Method and apparatus for generation of multiphase stochastic binary string

Abstract

Some of the disclosed methods and apparatuses use several types of stochastic binary string (SBS) generators to generate SBS sequences based on the particular values to be multiplied. Some embodiments use a multiphase SBS generator to more efficiently generate multiple SBS sequences that are offset from one another in “phase”.

Claims

1. A multi-phase_stochastic binary string (SBS) generator, comprising: (a) a first multiplexer having: (1) an output, a select signal input; (2) an X input; and (3) a Y input; (b) a select comparator having: (1) a reference input; (2) a p input; (3) an i input and an output coupled to the select signal input of the first multiplexer; (c) a phase index counter having: (1) a clock signal input; (2) a reset input; and (3) an output, the output coupled to the p input of the select comparator; (d) a bit index counter having: (1) an output coupled to the i input of the select comparator; and (2) an increment input; (e) a first summing circuit having: (1) a b input; (2) a 2.sup.L input; and (3) an output, the output coupled to the X input of the first multiplexer; (f) an accumulator having: an input coupled to the output of the first multiplexer; and (2) an accumulator output; (g) a second multiplexer having: (1) an output; (2) a select input; (3) an X input; and (4) a Y input, the X input being coupled to the output of the accumulator; (h) a subtraction circuit having: (1) an A.sub.i input coupled to the output of the accumulator; (2) a 2.sup.L input; and (3) an output coupled to the Y input of the second multiplexer; (i) a first comparator having: (1) an A.sub.i input coupled to the output of the accumulator; (2) a reference input; (3) a 2.sup.L input; and (4) an output coupled to the select input of the second multiplexer; (j) an 2.sup.L register having: (1) an 2.sup.L output coupled to the 2.sup.L input of the first summing circuit, to the 2.sup.L input of the first comparator and to the 2.sup.L input of the subtraction circuit; (k) a b register having: (1) a b output coupled to the b input of the first summing circuit; and (l) a second summing circuit having: (1) an output; (2) an A.sub.i input coupled to the output of the second multiplexer; and (3) a (p/m)2.sup.L input; (m) a (p/m)2.sup.L register having: (1) a p input coupled to the p output of the phase index counter; (2) an 2.sup.L input coupled to the 2.sup.L output of the 2.sup.L register; (3) an m input; and (4) a (p/m)2.sup.L output coupled to the (p/m)2.sup.L input of the second summing circuit; (n) an m register having: (1) an m output coupled to the m input of the (p/m)2.sup.L register; (o) a third summing circuit having: (1) a first input coupled to the output of the second summing circuit; (2) a b input coupled to the b output of the b register; (3) a 2.sup.L−1 input; and (4) an output; (p) a shift register having: (1) a 2.sup.L input coupled to the 2.sup.L output of the 2.sup.L register; and (2) a 2.sup.L−1 output coupled to the 2.sup.L−1 input of the third summing circuit; (q) a second comparator having: (1) a non-inverting input coupled to the output of the third summing circuit; (2) an inverting input coupled to the output of the 2.sup.L register; and (3) an output; (r) a memory device having: (1) an input coupled to the output of the second comparator; (2) a p input coupled to the p output of the phase index counter; and (3) an i input coupled to the i output of the bit index counter; (s) a clock source having: (1) a clock signal output coupled to the clock signal input of the phase index counter; (t) a third comparator having: (1) a non-inverting input coupled to the p output of the phase index counter; (2) an inverting input coupled to a reference value; and (3) an output coupled to the reset input of the phase index counter and to the increment input of the bit index counter; and (u) a fourth summing circuit having: (1) an A.sub.i input coupled to the A.sub.i output of the second multiplexer; (2) a b input coupled to the b output of the b register; (3) a 2.sup.L−1 input coupled to the 2.sup.L−1 output of the shift register; and (4) a Y output coupled to the Y input of the first multiplexer.

Description

DESCRIPTION OF THE DRAWINGS

(1) FIG. 1a through FIG. 1c illustrate an “ideal” bipolar SBS sequence N that represents a value of 2.

(2) FIG. 2 is an illustration of a circuit (i.e., an AND gate) for multiplying two USBS sequences.

(3) FIG. 3 is an illustration of two USBS sequences that are fully correlated.

(4) FIG. 4 is an illustration of two USBS sequences that are anti-correlated.

(5) FIG. 5 is an illustration of two USBS sequences in which half the bits are assigned a value of “1” are correlated with bits of the other string that are assigned a value of “1”.

(6) FIG. 6 is an illustration of an XNOR gate used to multiply two BSBS sequences.

(7) FIG. 7 is an illustration of a case in which two strings representing values of 0 are fully correlated.

(8) FIG. 8 is an illustration of a case in which the two strings representing values of 0 are fully anti-correlated.

(9) FIG. 9 is a simplified schematic of a design of an SBS generator, such as the one described above that can be used to generate an SBS sequence having a value that is determined by a stored binary value.

(10) FIG. 10 is a flowchart of an algorithm that is used in some embodiments of the δ-sequence generator to distribute the ones evenly throughout the δ-sequence.

(11) FIG. 11 through FIG. 15 provide a graphic representation of the steps shown in the flowchart of FIG. 10.

(12) FIG. 12 illustrates the condition once the index i is incremented from zero to 1.

(13) FIG. 13 illustrates incrementing the bit index, i to 2 and the calculation of the value of A.sub.2.

(14) FIG. 14 illustrates the next pass, in which the index is incremented to i=3.

(15) FIG. 15 illustrates the next pass, in which the index is incremented to i=4.

(16) FIG. 16 illustrates the result for each of the bits n.sub.0 through n.sub.15.

(17) FIG. 17 is an illustration of one embodiment for implementing the δ-sequence.

(18) FIG. 18 is an illustration of a first sequence N.sub.0 and a second sequence N.sub.1, in which the second sequence N.sub.1 is offset from the first sequence N.sub.0 by two bit positions.

(19) FIG. 19 is a flowchart of an embodiment of a multi-phase δ-sequence generator.

(20) FIG. 20 is an illustration of a vector chart showing a vector circle and pointers providing a graphical representation of the values that are calculated in the first pass through STEP 1901 through STEP 1905 of FIG. 19 to initialize the value of the accumulator A.sub.i to a value of A.sub.0.

(21) FIG. 21 illustrates STEP 1907 and STEP 1909 in which Bit 0, n.sub.0,0 of Phase 0 is generated.

(22) FIG. 22 is a graphical representation of the calculation of the sum in EQ. 11 for Bit 0, n.sub.1,0 of Phase 1.

(23) FIG. 23 is a graphical representation of the calculation of the sum in EQ. 18 for Bit 0, n.sub.2,0 of Phase 2.

(24) FIG. 24 is a graphical representation of the calculation of the sum in EQ. 21 for Bit 0, n.sub.3,0 of Phase 3.

(25) FIG. 25 illustrates the update of the value A.sub.i stored in the accumulator from A.sub.0 to A.sub.1.

(26) FIG. 26 is a graphical illustration of the process performed in STEP 1907 for a phase index value p=0 and a bit index value i=1.

(27) FIG. 27 is a graphical illustration of the process for a phase index value p=1 and a bit index value i=1 for generating Bit 1 of Phase 1.

(28) FIG. 28 is a graphical illustration of the process for a phase index value p=2 and a bit index value i=1.

(29) FIG. 29 is a graphical illustration of the process for a phase index value p=3 and a bit index value i=1.

(30) FIG. 30 illustrates the update of the accumulator A from A.sub.1 to A.sub.2 upon incrementing the bit index i to 2.

(31) FIG. 31 is a graphical illustration of the process for a phase index value p=0 and a bit index value i=2.

(32) FIG. 32 is a graphical illustration of the process for a phase index value p=1 and a bit index value i=2.

(33) FIG. 33 is a graphical illustration of the process for a phase index value p=2 and a bit index value i=2.

(34) FIG. 34 is a graphical illustration of the process for a phase index value p=3 and a bit index value i=2.

(35) FIG. 35 illustrates the update of the value A.sub.1 stored in the accumulator from A.sub.2 to A.sub.3.

(36) FIG. 36 is a graphical illustration of the process for a phase index value p=0 and a bit index value i=3.

(37) FIG. 37 is a graphical illustration of the process for a phase index value p=1 and a bit index value i=1 for generating Bit 1 of Phase 1.

(38) FIG. 38 is a graphical illustration of the process performed in STEP 1907 for a phase index value p=2 and a bit index value i=3.

(39) FIG. 39 is a graphical illustration of the process for a phase index value p=3 and a bit index value i=3.

(40) FIG. 40 shows the value of each of the bits from i=0 to i=15 for each of the four sequences generated in each phase (p=1 through p=3).

(41) FIG. 41 is a simplified schematic of one embodiment for implementing a multiphase δ-sequence generator.

(42) FIG. 42 is a simplified schematic illustrating single node 4200 of a neural network within an artificial intelligence engine.

(43) FIG. 43 is a simplified schematic of a portion of a neural network within an artificial intelligence engine.

(44) Like reference numbers and designations in the various drawings indicate like elements.

DETAILED DESCRIPTION

(45) Some embodiments of the disclosed method and apparatus use several types of stochastic binary string (SBS) generators to generate SBS sequences based on the particular values to be multiplied. Some embodiments use a multiphase SBS generator to more efficiently generate multiple SBS sequences that are offset from one another in “phase”, as will be explained in more detail below.

(46) δ-Sequence Generator

(47) One type of SBS generator that can be used in accordance with some embodiments of the disclosed method and apparatus generates an δ-sequence. A δ-sequence is a string that presents a numerical value in either unipolar or bipolar SBS format. The δ-sequence may be used either once or repeated multiple times within an SBS sequence. The δ-sequence evenly spreads the bit positions of the “1”s in the BSBS sequence out so that the “1”s are as evenly spaced across the string as possible.

(48) FIG. 10 is a flowchart of an algorithm that is used in some embodiments of the δ-sequence generator to distribute the ones evenly throughout the δ-sequence. The δ-sequence N is a string N.sub.1 of L bits in which the index i is an integer from 0 to 2.sup.L−1. To start, a bit index counter 1701 is initialized to zero and an accumulator A having a bit precision of L+1 is initialized to a value of A.sub.i=2.sup.L+b (STEP 1001). As noted above, the value of b is the value to be represented by the δ-sequence (i.e., the value to be converted from a two's complement binary representation to BSBS representation). It should be noted that for values b represented in two's complement, b will be in the range of −2.sup.L−1 to 2.sup.L−1−1. For example, for a two's complement representation in which L=4 can represent values b in a range from −8 to 7.

(49) It should be noted that a 4-bit two's complement binary number has a bit precision of 4 bits that represents the magnitude of the value. Two's complement binary numbers represent a range of positive and negative numbers by having the most significant bit represent a negative weight. Accordingly, a two's complement representation of the value 4, is b=0100. Accordingly, for L=4: the magnitude is represented as a value from −2.sup.L=2.sup.3=−8 to 2.sup.L−1=7. That is, the range of values that can be represented by b includes 1000=−8 to 0111=7. According, the maximum value that can be represented by b is 7=2.sup.L−1=2.sup.3−1. A 4-bit two's complement representation of the value −4 is b=1011. The lead bit indicates that the value represented by the following three bits is negative; in this case the following three bits being 011 indicate the magnitude is 4.

(50) By initializing the value of an accumulator, A.sub.0 to 2.sup.L+b, the value of the accumulator, A.sub.0 is initialized to b, offset by the total number of values that b can represent. However, it should be noted that in an alternative embodiment, the accumulator could be initialized to any value, since the process is periodic with a period of 2.sup.L. Once initialized, the value A.sub.0 of the accumulator A is then compared to 2.sup.L to determine whether it is greater than 2.sup.L (STEP 1003). In other embodiments, the comparison can be made to other values within a range from zero to 2.sup.L. If the comparison of STEP 1003 is true, then a bit n.sub.i of the δ-sequence, N is set to “1”. In some embodiments, the value of the accumulator is maintained within a range of zero to 2.sup.L. This can be done by decrementing the value A.sub.i of the accumulator, A by 2.sup.L if it is greater than 2.sup.L (STEP 1005). Alternatively, the accumulator can roll over to zero when incremented by one from the value 2.sup.L−1. If the comparison of STEP 1003 is false, the bit n.sub.i of the δ-sequence, N is set to “0” and the value A.sub.i of the accumulator, A remains the same (STEP 1007). In either case, the index i is then incremented (STEP 1009). After incrementing the index, the index i is checked to see whether all of the bits of the δ-sequence, N have been generated (STEP 1011). Since they have not, the value A.sub.i of the accumulator is updated to A.sub.i=A.sub.i−1+b+2.sup.L−1 (STEP 1013).

(51) FIG. 11 through FIG. 15 provide a graphic representation of the steps shown in the flowchart of FIG. 10. In FIG. 11, a vector circle 1100 is shown having a period of 2.sup.L, with zero/2.sup.L at the top (i.e., at zero degrees, top center, “12-o'clock”). Values represented around the circle increase linearly from 0 to 2.sup.L in a clockwise direction around the circle over 360 degrees. In the example shown, L=4 and b=4. The circle 1100 illustrates the state of the accumulator A with the index, i=0. A first pointer 1102 is shown at position “1”, representing a value of 2.sup.L=2.sup.4=16. A pointer 1104 is rotated 90° clockwise with respect to the pointer 1102 to a position “2”, representing A.sub.0=2.sup.L+b=16+4=20 (i.e., the point on the circle representing the value A.sup.0 to which the accumulator A is initialized at STEP 1001, with the index i=0), as indicated by an arrow 1106. Upon performing a comparison in STEP 1003, the value of A.sub.0=20 is determined to be greater than 2.sup.L=16. Accordingly, on the first pass through STEP 1003, the answer is “true”. STEP 1005 is performed and the value of Bit 0, n.sub.i=n.sub.0 for i=0 is set to “1”. The bits n.sub.0−n.sub.15 of the δ-sequence, N are shown, with the value of no set to 1. In addition, the value A.sub.0 of the accumulator A with a bit index equal to zero (indicated by the subscript) is reduced by 2.sup.L. Accordingly, A.sub.0=A.sub.0−2.sup.L=20−16=4, as shown by the 360° counter-clockwise rotation of the pointer 1104 indicated by the arrow 1108 to result in a pointer 1110 located at position “3”, which is the collocated with position “2” of the pointer 1104. Note that a series of numbers from “1” to “3” are shown on the pointers 1102, 1104, 1110 to indicate the order of the rotation of the pointers around the vector circle 1100.

(52) Note that the index is not yet incremented. It should also be noted that in some embodiments in which 2.sup.L=16, the accumulator A is a 4-bit register that will overflow at count 16, making the content of the accumulator at A.sub.0 equal to b=4, thus negating the need to subtract 2.sup.L from the value in the accumulator A.sub.0. However, in such embodiments, the test performed in STEP 1003 is more complicated, since there is a need to determine whether the pointer has rotated past zero, rather than simply testing for a value greater than 2.sup.L.

(53) FIG. 12 illustrates the condition once the index i is incremented from zero to 1 (STEP 1009). Next, the index i is then checked to see whether all of the bits of the δ-sequence, N have been generated (STEP 1011). Since they have not, STEP 1013 is performed, in which the next value A.sub.1 is calculated as A.sub.1=A.sub.0+b+2.sup.L−1=4+4+8=16 (STEP 1013). The pointer 1110 at position “3” representing the current value of A.sub.0 is first rotated 90° clockwise by the value b, illustrated by the arrow 1204, resulting in a pointer 1206 at position “4”. The pointer 1206 is then rotated another 180° to the top of the circle 1200 as indicated by arrow 1210, illustrating the addition of the value of 2.sup.L−1=8, resulting in pointer 1208 at position “5”. The process then returns to STEP 1003 and the value A.sub.1 is compared to 16 (STEP 1003). Since A.sub.1=16, the result of the compare is true and the value of n.sub.1 is set to 1 (STEP 1005). It can be seen that each time the value of the accumulator is updated in STEP 1013, a check is made at STEP 1003 to see whether the pointer representing the value of the accumulator has rotated to, or past, the top of the vector circle 1100. If not, the associated bit is set to “0”; if so, the associated bit is set to “1”. The smaller the value b, the more bits will be set to zero, since it will take more passes through STEP 1013 to cause the pointer to rotate to the top of the vector circle 1100. At the one extreme (i.e., when b=−8), the increment added to A.sub.i in STEP 1013 will be zero (i.e., b+2.sup.L−1=−8+8=0). Therefore, all of the bits will be set to “0”. In the other extreme (i.e., when b=7), the increment added to A.sub.i will be 15 (i.e., b+2.sup.L−1=7+8). Therefore, for each of the 16 bits, the sum in STEP 1003 will be greater than or equal to 16. It should be noted that the when the bit index i=0, the sum in STEP 1011 will be equal to 31 and after incrementing the bit index i to a value of 15, the sum A.sub.15 in STEP 1013 will be equal to 16. Accordingly, upon making the last pass through STEP 1009 all of the bits will have been set to “1”.

(54) When the pointer 1208 representing the value of the accumulator for the next index value i has rotated to or past the top, the value of the accumulator A.sub.1 is reduced by 2.sup.L (STEP 1005) as illustrated by the arrow 1212 indicating a 360° counter-clockwise rotation of the pointer 1208 back to a value of zero. The resulting value is represented by a pointer 1214 at position “6”.

(55) FIG. 13 illustrates incrementing the bit index, i to 2 (STEP 1009) and the calculation of the value of A.sub.2=A.sub.1+b+2.sup.L−1=0+4+8=12 (STEP 1013). The pointer 1214 at position “6” represents A.sub.1, the current value of the accumulator. Adding the value b is shown by an arrow 1302 representing a 90° clockwise rotation of the pointer 1214 resulting in a pointer 1304 at position “7”. The addition of the value 2.sup.L is shown by an arrow 1306 representing a 180° clockwise rotation of the pointer 1404, resulting in a pointer 1308 at position “8”, indicating a value of A.sub.2=12. Since A.sub.2=12 is less than 2.sup.L=16, the value of the bit n.sub.2 as determined in STEP 1005 is set to 0.

(56) FIG. 14 illustrates the next pass through STEP 1009, in which the index is incremented to i=3. The bit index i is then checked to see whether all of the bits of the δ-sequence, N have been generated (STEP 1011). Since they have not, a new value is calculated for A.sub.3=A.sub.2+b+2.sup.L−1=12+4+8=24 (STEP 1013). An arrow 1404 shows the 270° clockwise rotation of the pointer 130 from position “8” representing the addition of the value b+2.sup.L=12 to pointer 1402 at position “9” having a value of 24. The process then returns to STEP 1003. In STEP 1003, A.sub.3=24 is compared to 2.sup.L=16. Since A.sub.3=24 is greater than 2.sup.L, the value of n.sub.3 is set to 1 and a new value is calculated for A.sub.3 in STEP 1005. The new value is A.sub.3=A.sub.3−2.sup.L=24−16=8, which rotates the pointer 1402 from position “9” counter-clockwise by 360° to position “10”, as indicated by the arrow 1406.

(57) FIG. 15 illustrates the next pass through STEP 1009, in which the index is incremented to i=4. The index i is then checked to see whether all of the bits of the δ-sequence, N have been generated (STEP 1011). Since they have not, a new value is calculated for A.sub.4=A.sub.3+b+2.sup.L−1=8+4+8=20 (STEP 1013). An arrow 1504 shows the 270° clockwise rotation of the pointer 1302 at position “10”, resulting in a pointer 1502 at position “11”. The process then returns to STEP 1003. In STEP 1003, A.sub.4=20 is compared to 2.sup.L=16. Since A.sub.4 is greater than 2.sup.L, the value of n.sub.4 is set to 1 and a new value is calculated for A.sub.4 in STEP 1005. The new value is A.sub.4=A.sub.4−2.sup.L=20−16=4, which rotates the pointer 1502 from position “11” 360° counter-clockwise, as indicated by arrow 1506, resulting in pointer 1508 at the position “12”. It can be seen that the pointer 1508 at position “12” has the same value as the pointer 1104 at position “2” show in FIG. 11, when the index value was i=0. Accordingly, when the index increments to i=5, the process will proceed exactly as it did when the index incremented to i=1. Therefore, it can be seen that the value of the bit n.sub.5 will be set to 0 and the value of A.sub.5 will be calculated to be the same as the value of A.sub.i=16. Similarly, the value of the bit n.sub.6 will be set to 1, the same as bit n.sub.2 and the value of A.sub.7 will be calculated to be the same as the value of A.sub.3=12. This pattern will continue for all the remaining bits from n.sub.7 through n.sub.15, with bit n.sub.15 having the same value as bit n.sub.3. The index i is checked to see whether all of the bits of the δ-sequence, N have been generated (STEP 1011). Once the index i, is equal to 2.sup.L=16 the process ends.

(58) FIG. 16 illustrates the result for each of the bits n.sub.0 through n.sub.15. As can be seen from the values of the bits n.sub.0-n.sub.15, the ones and the zeros have been evenly distributed over the 16 bits of the δ-sequence N. For each bit that is equal to zero, there are three bits that are ones.

(59) FIG. 17 is an illustration of one embodiment for implementing the 6-sequence 1700. Initially, a bit index counter 1701 is initialized to a count of i=0. A clock 1702 coupled to the bit index counter 1701 increments the bit index counter 1701 to a terminal value of 2.sup.L−1, at which point the bit index counter 1701 wraps around to zero (i.e., modulo 2.sup.L). The output of the bit index counter 1701 is coupled to the input of a comparator 1703. The comparator 1703 generates a select signal by comparing the index value i output from the bit index counter 1701 to zero. If i=zero, the select signal is one; otherwise, the select signal is zero. The select signal is coupled to a first select input to a multiplexer 1704 that selects between coupling a second 2.sup.L−1 input and a third b input to an output of an A.sub.i−1 input to the multiplexer 1704. In accordance with some embodiments of the disclosed method and apparatus, the 2.sup.L−1 input is coupled a register 1714 that holds the value 2.sup.L-1. The output of the register 1714 is coupled to the input of a right shift register 1716. In such embodiments, the value 2.sup.L−1 is derived by performing a right shift of the output of the register 1714. Alternatively, a register (not shown) stores the value 2.sup.L-1.

(60) The A.sub.i−1 input to the multiplexer 1704 is coupled to the output of an Accumulator A 1705. A memory register 1707 in which the value b is stored provides the value b to be converted from a two's complement binary representation to a BSBS sequence to the b input of a summing circuit 1706.

(61) The output of the summing circuit 1706 is the sum of the three outputs A.sub.i−1+b+2.sup.L−1 that is equal to an intermediate value of A.sub.i. Note that when the index value i is equal to zero, an initialization value of 2.sup.L−1 is used in this sum rather than the value stored in Accumulator A 1705. That is, by selecting an initialization value rather than the value of the Accumulator A 1705, the value at which the process starts is initialized to 2.sup.L−1+b+2.sup.L−1=2.sup.L+b (see STEP 1001 in flowchart of FIG. 10).

(62) The intermediate value of A.sub.i is coupled to three different inputs. The first of these inputs is a positive input to a comparator 1708. The second is an input to a difference circuit 1710. The third is an input to a multiplexer 1712. The negative input to the comparator 1708 is coupled to the register 1714 in which the value 2.sup.L is stored. If the positive input is greater than the negative input, then the output of the comparator 1708 is a one. That is, if the sum A.sub.i=A.sub.i−1+b+2.sup.L−1 produced by the summing circuit 1706 is greater than 2.sup.L then the comparator outputs a “1”. Otherwise, the comparator outputs a “0”.

(63) The output of the comparator 1708 is coupled to the select input of the multiplexer 1712. When the comparator outputs a “1”, the multiplexer 1708 couples the “x” input to the output of the multiplexer 1708. The “x” input to the multiplexer 1708 is coupled to the output of the difference circuit 1710. The difference circuit 1710 outputs the difference between 2.sup.L and the intermediate value of A.sub.i. When the comparator 1708 outputs a “0”, the multiplexer 1710 couples the intermediate value of A.sub.i to the output of the multiplexer 1710. The output of the multiplexer 1712 is coupled to the input of the accumulator A 1705. A clock, which may either be the clock that increments the bit index counter 1701 or a clock derived from that clock, determines when the value A.sub.i should be updated.

(64) Accordingly, when the intermediate value of A.sub.i, which is the sum A.sub.i−1+b+2.sup.L−1 is greater than 2.sup.L (see STEP 1003), the multiplexer 1712 sets the value of A.sub.i equal to the intermediate value of A.sub.i (see STEP 1011) minus 2.sup.L (see STEP 1005). Alternatively, when the intermediate value of A.sub.i (i.e., the sum A.sub.i−1+b+2.sup.L−1) is less than, or equal to 2.sup.L, the multiplexer 1712 maintains the value of A.sub.i to be equal to the intermediate value of A.sub.i output from the summing circuit 1706 (see STEP 1011).

(65) The output of the comparator 1708 is also coupled to the input to an N register 1718 that holds the values of each of the bits n.sub.i of the δ-sequence N. The index i is used to save the bits n.sub.i of the δ-sequence in distinct bit locations associated with the value of the index i. It should be noted that the δ-sequence generator 1700 comprises very simple circuit element, such as a bit index counter 1701, a summing circuit 1706, a difference circuit 1710, 2 comparators 1703, 1708, 2 multiplexers 1704, 1712, a shift register 1716 and four registers 1705, 1707, 1714, 1718.

(66) A BSBS sequence generated using a 6-sequence has several properties of interest. The first of these properties is that the maximum error for the δ-sequence is less than 1/T. That is, converting a binary value to a BSBS sequence, and then converting the BSBS sequence back to a binary number will result in an error that is less than 1/T, where T is the length of the δ-sequence. Another property of a BSBS sequence generated with an δ-sequence is that it can be generated without the use of a random number generator. Yet another property of a BSBS that has been generated with an δ-sequence is that the BSBS sequence will have the maximum number of transitions possible (state changes between one and zero). However, an accurate product cannot be obtained when multiplying a BSBS sequence that has been generated using a 6-sequence generator with another BSBS sequence that has been generated using a 6-sequence. Neither can an accurate product be attained when multiplying a BSBS sequence that has been generated using a 6-sequence with a time-shifted version of itself. Nonetheless, a BSBS sequence that has been generated using an w-sequence (i.e., a sequence in which the “1”s are all grouped together and the “0”s are all grouped together) can be multiplied with a BSBS sequence that has been generated using a δ-sequence.

(67) Multiphase δ-Sequence Generator

(68) In some embodiments, the δ-sequence generator is implemented as a multi-phase δ-sequence generator. A multi-phase δ-sequence generator is a δ-sequence generator in which more than one δ-sequence is generated concurrently. Each of the δ-sequences, N.sub.p represents the same binary value b, but is “offset in phase” from the other δ-sequences that are concurrently generated. A second sequence, N.sub.1 is considered to be offset in phase from a first sequence, N.sub.0 when the bits generated for the second sequence are the same as those generated for the first sequence, but are shifted in location along the sequence. Accordingly, bits n.sub.0,i of the first sequence N.sub.0 have the same value as bits n.sub.1,i−4 of the second sequence N.sub.1.

(69) FIG. 18 is an illustration of a first sequence N.sub.0 and a second sequence N.sub.1, in which the second sequence N.sub.1 is offset from the first sequence N.sub.0 by two bit-positions. Accordingly, it can be seen that each bit n.sub.0,i of the first sequence N.sub.0 has the same value as the bit n.sub.i,i−2 of the second sequence N.sub.1. For example, the bit n.sub.0,2 has the same value as the bit n.sub.1,0. The bit n.sub.0,3 has the same value as the bit n.sub.1,1. The bit n.sub.0,4 has the same value as the bit n.sub.1,2. The bit n.sub.0,5 has the same value as the bit n.sub.1,3. And so on.

(70) Two new variables, in addition to the variables defined for the δ-sequence generator above, are defined for the multi-phase δ-sequence. The first new variable is m, indicating the total number of δ-sequences that will be generated (i.e., the number of “phases”). The second new variable is a phase index, p having a value from 0 to m−1 and indicating the particular phase at issue (not to be confused with p as used above to represent the probability that a bit in the sequence is a “1”). For ease in describing the disclosed method and apparatus, each δ-sequence is referred to as a “phase”, N.sub.p that is generated in association with a phase index, p and has a string of bits n.sub.p,i, where i is a bit index of the particular bit n.sub.p,i, of the δ-sequence, Np. Accordingly, the 1.sup.st bit (“Bit 0”) of the first phase N.sub.0 (“Phase 0”) that is output from the generator is n.sub.0,0, and the 5.sup.th bit (“Bit 4”) of the second phase N.sub.1 (“Phase 1”) that is output from the generator is n.sub.1,4. FIG. 18 provides an example of the manner in which the bits are of two phases are referenced.

(71) FIG. 19 is a flowchart of an embodiment of a multi-phase δ-sequence generator. The process for generating the δ-sequences starts with the initialization of the value of the bit index i, phase index p, and the value A.sub.i stored in a shared accumulator (STEP 1901). The bit index i and the phase index p are initialized to the value 0. The value A.sub.0 of the accumulator is initialized to:
A.sub.0=2.sup.L+b.  EQ. 1

(72) The same accumulator can be used to generate the δ-sequence for each phase of the multiple δ-sequence. After initializing the value A.sub.0, the value is checked to see whether it is greater than 2.sup.L or not. If greater (i.e., the result of STEP 1903 is true), the value of A.sub.0 is reduced by 2.sup.L (STEP 1905). If, on the other hand, the result is false, no reduction of the value of A.sub.0 is required. In either case, a check is made (STEP 1907) to see whether the following logic statement is true:
Mod 2.sup.L(A.sub.i+(p2.sup.L)/m)+b+2.sup.L−1>=2.sup.L  EQ. 2

(73) In all cases, b is in a range from −2.sup.L−1 to 2.sup.L−1, therefore, b+2.sup.L−1 will be in the range of 0 to 2.sup.L. The comparison of STEP 1907 checks whether the modulo 2.sup.L value of A.sub.i+(p 2.sup.L)/m) plus the value of b+2.sup.L−1 is greater than or equal to 2.sup.L. This compare step is essentially the same as the compare performed in STEP 1011 (see FIG. 10) for the single phase δ-sequence generator, but with an offset to the value of the accumulator A that is dependent upon the value of the phase index, p. For the phase in which p is zero (the zero-phase offset, or the “baseline δ-sequence”), the offset is zero. That is, the offset factor 2.sup.L/m is multiplied by the value of p=0 and the comparison in STEP 1907 essentially determines whether Ai+b+2.sup.L−1 is greater than 2.sup.L, similar to the STEP 1011. For other values of p, the offset is a fraction of 2.sup.L that is equal to (p/m)2.sup.L. In one example that is discussed here, there are 4 phases (i.e., four δ-sequences) generated. In this example, m=4 and p is a value from 0 to 3. The first δ-sequence is the baseline with a zero phase offset, the second has phase offset that is equal to ¼ of the period, where the period is equal to 2.sup.L. The third δ-sequence has a ½ period phase offset, and the fourth has a ¾ period phase offset, where 2.sup.L is the length of the period. If there are 8 phases (i.e., eight δ-sequences) generated, then m=8 and the first δ-sequence for which p=0 is the baseline (zero phase offset), the second δ-sequence for which p=1 is offset by 2.sup.L times p/m=2.sup.L (1/8), the third δ-sequence for which p=2 is offset by 2.sup.L times p/m=2.sup.L (2/8)=2.sup.L(1/4), etc.

(74) If the comparison in STEP 1907 is true, then the value of Bit 0, n.sub.0,0 of Phase 0 is set to “1” (STEP 1909), and if false, the bit is set to “0” (STEP 1911). The phase index p is then incremented (STEP 1913). The value of the phase index p is checked to see whether Bit 0 in each phase has been determined (STEP 1913). If not, state of Bit 0 of the next phase is set depending upon whether the comparison in STEP 1907 is true or false. When the phase index p reaches m (STEP 1915), the first bit of each sequence will have been set. In an alternative embodiment, the phase index p roles over to zero on the next count after p=m−1. In some such embodiments, a comparison is made in STEP 1915 to determine whether p=0. The bit index i is then incremented and the phase index p is reset to zero (STEP 1917). The value of the bit index i is checked to see whether all of the bits of each phase have been generated (STEP 1919). If not, then the value of the shared accumulator A is incremented by b+2.sup.L−1 (STEP 1921) and the process repeats from STEP 1903 to generate the next bit of each phase. If, however, the value of the bit index i is equal to 2.sup.L (STEP 1919), then all of the bits for all of the phases have been generated. In that case, the process ends (STEP 1923). Similar to the phase index, the bit index i may role over to zero in the next count after i=2.sup.L−1. In that case the bit index i is compared to zero to determine whether all of the bits have been generated.

(75) Generation of Bit 0 (i.e., the First Bit)

(76) FIG. 20 is an illustration of a vector chart showing a vector circle 2000 and pointers providing a graphical representation of the values that are calculated in the first pass through STEP 1901 through STEP 1905 to initialize the value of the accumulator A.sub.i to a value of A.sub.0. In the example, the generator at issue is a 4-phase δ-sequence generator (i.e., where m=4, p=0 and i=0). In addition, in this example, each of the four SBS strings in each of the four phases (“Phase 0”, “Phase 1”, “Phase 2” and “Phase 3”) to be generated represent a value b=4 and where the length (number of bits) L of the binary value b is 4.

(77) Initially, a pointer 2002 points straight up at “12-o'clock” and represents the value 2.sup.L=16. A reference number “1” on the pointer 2002 indicates that the pointer 2002 is in position “1” in the process shown in FIG. 20. The pointer 2002 is rotated 90° clockwise, as indicated by the arrow 2003. This rotation illustrates the addition of the value b to attain the initial value of the accumulator A.sub.0, and results in a pointer 2004 being located at position “2”, indicated by the reference number “2” on the pointer 2004. That is, the pointer 2104 at position “2” represents the value 2.sup.L+b to which A.sub.0 is initialized in STEP 1901:
A.sub.0=2.sup.L+b=16+4=20  EQ. 3

(78) Since the value of A.sub.0 is greater than 2.sup.L (STEP 1903), the value of the accumulator is reduced by 2.sup.L (STEP 1905). Therefore:
A.sub.0=A.sub.0−2.sup.L=  EQ. 4
A.sub.0=20−16=4  EQ. 5

(79) STEP 1903 and STEP 1905 ensure that the value A.sub.i of the accumulator remains in the range of 0 to 2.sup.L−1. This is illustrated by the pointer 2004 rotating counter-clockwise 360°, as indicated by arrow 2005, resulting in the pointer 2006 coming to rest at position “3” indicated by the reference number “3” on the pointer 2006. It can be seen that each time the value of the accumulator is altered (i.e., in STEP 1901 initially, and then in STEP 1921 as the process moves on), the value of the accumulator is checked to ensure the value is less than 2.sup.L (STEP 1903 and STEP 1905). In some embodiments, this might be done simply by having the accumulator be a register that overflows at 2.sup.L and rolls back to zero. Accordingly, the pointer 2006 represents the value A.sub.0 of the accumulator with the bit index i=0.

(80) Generation of Bit 0, n.sub.0,0 of the First Phase (i.e., Phase 0)

(81) FIG. 21 illustrates STEP 1907 and STEP 1909 in which Bit 0, n.sub.0,0 of Phase 0 is generated. The sum of STEP 1907 is calculated in EQ. 6:
Mod 2.sup.L(A.sub.0+(p/m)2.sup.L)+b+2L.sup.−1=  EQ. 6

(82) The first term (Mod 2.sup.L(A.sub.0+(p/m)2.sup.L)) of EQ. 2 represents the value of the accumulator plus a phase offset. Since this first term is operated on by the Modulo 2.sup.L operator, the value will always be in the range of 0 to 2.sup.L. In the current example, first term resolves to a value of 4, as shown in EQ. 7 through EQ. 10 below. It can be seen that the phase offset (i.e., second term within the parenthesis of the Modulo 16 operation (i.e., (p/m)2.sup.L)) is equal to zero for Phase 0 in which the phase index, p=0.
Mod 2.sup.L(A.sub.0+(p/m)2.sup.L)=  EQ. 7
Mod 2.sup.L(4+(p/m)2.sup.L)=  EQ. 8
Mod 16((4)+(0/4)16)=  EQ. 9
Mod 16(4)=4.  EQ. 10

(83) The pointer 2006 is shown in red in FIG. 21 to highlight the reference pointer provided by the value A.sub.0 held in the accumulator A plus the phase offset (A.sub.i+(p/m)16). Adding the second term of EQ. 2 (the value of b=4) rotates the pointer 2106 from position “3” clockwise by 90° to pointer 2108 at position “4”, as indicated by arrow 2107. Adding another 8 (i.e., the value of 2.sup.L−1, the third term of EQ. 2), rotates the pointer 2108 to pointer 2110 at position “5”, as indicated by the arrow 2109. The pointer 2110 represents the value that is compared in STEP 1907 to the value of 2.sup.L. That is, the pointer 2110 represents a value of:
Mod 16(A.sub.0+(p/m)2.sup.L)+b+2.sup.L−1=  EQ. 11
Mod 16(4+(0/4)16)+4+8=  EQ. 12
Mod 16(4)+4+8=  EQ. 13
4+4+8=16.  EQ. 14

(84) Since the result of the compare in STEP 1907 is true (i.e., the pointer 2110 has rotated up to at least the top of the vector circle 2000), Bit 0 of Phase 0 n.sub.0,0 is set to 1 (STEP 1909). The phase index, p is then incremented by 1 (STEP 1913) and the value of the phase index p is checked to see whether Bit 0 of each phase has been generated (STEP 1915).

(85) Generation of Bit 0, n.sub.1,0 of Phase 1

(86) Since only Bit 0 n.sub.0,0 of Phase 0 has been generated, the process moves on to generate Bit 0, n.sub.1,0 of Phase 1 by performing the compare in STEP 1907. Once again, the sum of EQ. 11 is calculated, but with the value of p incremented to a value of 1 (STEP 1915). The value of A.sub.0 remains the same (i.e., A.sub.0=4). Accordingly, the value of the equation of STEP 1907 is calculated as:
Mod 16(4+(1/4)16)+4+8=  EQ. 15
Mod 16(4+4)+4+8=  EQ. 16
8+4+8=20.  EQ. 17

(87) FIG. 22 is a graphical representation of the calculation of the sum in EQ. 11 for Bit 0, n.sub.1,0 of Phase 1. Calculation of the sum is shown in detail in EQ. 15 through EQ. 17 above. It should be noted that the value of A.sub.0 will not change as the sum of EQ. 17 is calculated, since the value of the accumulator A only changes after the bit index i is incremented (STEP 1917). Accordingly, the value of the accumulator A is updated in STEP 1921 after the ith bit of each phase has been determined and the bit index i has been incremented, assuming the terminal value i=2.sup.L has not yet been reached (STEP 1919).

(88) As noted above, the value of A.sub.0 is represented by the pointer 2106 at position “1”. The value of the phase offset (shown within the parenthesis of the modulo 16 operation in EQ. 11) is added, as indicated by the arrow 2202 shown outside the phase circle 2000, resulting in the pointer 2204 at position “2”. The arrow 2202 is shown outside the phase circle 2000 to distinguish it from the factors that are common to each phase, and to highlight the relative rotation that occurs by adding the phase offset. In addition, the pointer 2204 is red to further highlight the phase offset. The phase offset, (p/m)2.sup.L, is shown in EQ. 16 to be equal to 4.

(89) The next term of EQ. 11 (i.e., b) is added, as indicated by the arrow 2206, resulting in the pointer 2208 at position “3”. Lastly, the final term of EQ. 11 (i.e., 2.sup.L) is added, as indicated by the arrow 2210, resulting in the pointer 2212 at position “4”. As shown above in EQ. 17, the sum represented by the pointer 2212 is equal to 20.

(90) Since 20 is greater than 2.sup.L, the result of the compare in STEP 1907 is true for Bit 0, n.sub.1,0 of Phase 1. Accordingly, Bit 0″ n.sub.1,0 of Phase 1 is set to “1”. It can be seen that the positions 2, 3, and 4 of the pointers 2204, 2208, 2212 are each offset by 4 (i.e., 90° or ¼ of the way around the vector circle) with respect to the positions, 3, 4, 5, respectively, of the pointers 2006, 2108, 2110 shown in FIG. 21.

(91) The phase index, p is then incremented (STEP 1913) to a value of p=2 in order to determine the value of Bit 0, n.sub.2,0 of the next phase, “Phase 2”.

(92) Generation of Bit 0, n.sub.2,0 of Phase 2

(93) Once again, the sum of EQ. 11 is calculated. However, the value of p is incremented to 2 (STEP 1913). Accordingly:
Mod 16(4+(2/4)16)+4+8=  EQ. 18
Mod 16(4+8)+4+8=  EQ. 19
8+8+8=24.  EQ. 20

(94) FIG. 23 is a graphical representation of the calculation of the sum in EQ. 18 for Bit 0, n.sub.2,0 of Phase 2. It should be noted that the current value of A.sub.0 (i.e., the value to be used in EQ. 18), remains equal to 4 as represented in FIG. 23 by the pointer 2106. It should be further noted that the value of A.sub.0 will not change as the sum of EQ. 20 is calculated, since this sum is merely used to determine whether Bit 0, n.sub.1,0 of Phase 1 should be set to “1” or “0” (STEP 1907).

(95) The value of the phase offset within the parenthesis of the modulo 16 operation in EQ. 11 is added to A.sub.0, resulting in a clockwise 180° rotation to the pointer 2304 at position 2, as indicated by the arrow 2302. The phase offset, (p/m)2.sup.L, is shown in EQ. 19 to be equal to 8. The next term of EQ. 11 (i.e., b) is added, as indicated by the arrow 2306, resulting in the pointer 2308 at position 3. Lastly, the final term of EQ. 11 (i.e., 2.sup.L) is added, as represented by the arrow 2310, resulting in the pointer 2312 at position 4. As shown above in EQ. 20, the sum represented by the pointer 2312 is equal to 24. Accordingly, the positions 2, 3, and 4 of the pointers 2304, 2308, 2312 are each offset by 4 (i.e., 90° or ¼ of the way around the vector circle) with respect to the positions, 2, 3, 4, respectively, of the pointers 2204, 2208, 2212 shown in FIG. 22.

(96) Since 24 is greater than 2.sup.L, the result of the compare in STEP 1907 is true for Bit 0, n.sub.2,0 of Phase 2. Accordingly, Bit 0, n.sub.2,0 of Phase 2 is set to “1”. The phase index, p is then incremented (STEP 1913) to a value of 3 in order to determine the value of Bit 0, n.sub.3,0 of “Phase 3”.

(97) Generation of Bit 0, n.sub.3,0 of Phase 3

(98) Once again, the sum of EQ. 11 is calculated. However, the value of p is 3. Accordingly:
Mod 16(4+(3/4)16)+4+8=  EQ. 21
Mod 16(4+12)+4+8=  EQ. 22
0+4+8=12.  EQ. 23

(99) FIG. 24 is a graphical representation of the calculation of the sum in EQ. 21 for Bit 0, n.sub.3,0 of Phase 3. As noted above, the value of A.sub.0 remains equal to 4 as represented in FIG. 24 by the pointer 2106 at position “1”. The value of the phase offset, as indicated by the arrow 2402, rotation that results in the pointer 2404 at position “2”. The phase offset, (p/m)2.sup.L, is shown in EQ. 22 to be equal to 12. The next term of EQ. 11 (i.e., b) is added, as indicated by the arrow 2406, resulting in the pointer 2408 at position “3”. Lastly, the final term of EQ. 11 (i.e., 2.sup.L) is added, as represented by the arrow 2410, resulting in the pointer 2412 at position “4”. As shown above in EQ. 23, the sum represented by the pointer 2412 is equal to 12. The pointers at positions “2”, “3”, and “4” are each offset by 12 (i.e., 90° or ¼ of the way around the vector circle) with respect to the positions, “2”, “3”, “4”, respectively, of the pointers 2304, 2308, 2312 shown in FIG. 23.

(100) Since the sum shown in EQ. 23 is equal to 12 and is therefore less than 2.sup.L, the result of the compare in STEP 1907 is false for Bit 0, n.sub.3,0 of Phase 3. Accordingly, Bit 0, n.sub.3,0 of Phase 3 is set to “0”. The phase index, p is then incremented (STEP 1913) to a value of 4, indicating in STEP 1915 that the first bit of each of the four phases have now been set.

(101) It can be seen that for each successive phase of the 4-phase δ-generator, the value represented by each of the pointers (except the first pointer that represents the value A.sub.0 of the accumulator A), increases by 4 with respect to the similar pointer of the previous phase due to the value of the phase offset. This includes pointers representing the sum calculated in STEP 1907. This is illustrated by the relative rotation of each of the pointers by 90° in FIG. 21, FIG. 22, FIG. 23 and FIG. 24.

(102) In STEP 1917, the bit index i is incremented from zero to 1 to begin generating the second bit of each of the four sequences.

(103) Generation of “Bit 1” (i.e., the Second Bit)

(104) FIG. 25 illustrates the update of the value A.sub.i stored in the accumulator from A.sub.0 to A.sub.1 (STEP 1921 and STEP 1905). EQ. 24 through EQ. 27 below show the calculation of A.sub.1:
A.sub.1=A.sub.0+b+2.sup.L−1=  EQ. 24
A.sub.1=4+4+8=16  EQ. 25
A.sub.1=A.sub.1−2.sup.L=  EQ. 26
A.sub.1=16−16=0  EQ. 27

(105) The value b is added to A.sub.0, as indicated by the arrow 2507 illustrating the rotation of the pointer 2106 from position “1” representing a value of 4, to position “2” of the pointer 2508 representing a value of 8. 2.sup.L−1 is then added, as illustrated by the arrow 2509 showing the pointer 2508 at position “2” rotating 180° clockwise to pointer 2510 at position “3”. In some embodiments, the value A.sub.i stored in the accumulator should remain in the range of 0 to 2.sup.L−1 (i.e., between 0 and 15 in the example shown). Accordingly, if the value A.sub.1 is equal or greater than 2.sup.L (STEP 1903), it is reduced by 2.sup.L (STEP 1905). The pointer 2510 at position “3” representing a value of 16 is rotated counter-clockwise by 360°, as indicated by arrow 2512, resulting in the pointer 2514 at position “4” (STEP 1905) representing a value of 0.

(106) Generation of “Bit 1”, n.sub.0,1 of Phase 0

(107) FIG. 26 is a graphical illustration of the process performed in STEP 1907 for a phase index value p=0 and a bit index value i=1.
Mod 16(A.sub.1+(p/m)2.sup.L)+b+2.sup.L−1=  EQ. 28
Mod 16(0+(0/4)16)+4+8=  EQ. 29
Mod 16(0+0)+4+8=  EQ. 30
0+4+8=12  EQ. 31

(108) The value A.sub.1 can be seen from EQ. 27 to be equal to 0. A pointer 2514 at position “4” represents the value A.sub.1. The pointer 2514 is rotated 90° clockwise by the addition of b, as illustrated by the arrow 2602, resulting in the pointer 2604 at position “5”. The value 2.sup.L−1 is then added, resulting in a further 180° rotation of the pointer 2604, as illustrated by the arrow 2606 and resulting in the pointer 2608 at position “6” representing a value of 12. Since the sum of EQ. 33 represented by the pointer 2608 is less than 16 (i.e., 2.sup.L), Bit 1, n.sub.0,1 of Phase 0 will be set to “0”. That is, since the pointer 2514 representing the value A.sub.1 did not rotate up to or past the top of the vector circle 2000 when summed with b+2.sup.L−1 in STEP 1907, the bit is set to “0”.

(109) Generation of Bit 1, n.sub.1,1 of Phase 1

(110) FIG. 27 is a graphical illustration of the process performed in STEP 1907 for a phase index value p=1 and a bit index value i=1 for generating Bit 1 of Phase 1. EQ. 32 through EQ. 35 show the details of the calculation performed in STEP 1907.
Mod 16(A.sub.1+(p/m)2.sup.L)+b+2.sup.L−1=  EQ. 32
Mod 16(0+(1/4)16)+4+8=  EQ. 33
Mod 16(0+4)+4+8=  EQ. 34
4+4+8=16  EQ. 35

(111) As noted above in EQ. 27, the value A.sub.1=0 and remains the same for each phase until the bit index i is incremented in STEP 1917 (i.e., upon all of the second bits of each phase being set). The pointer 2514 at position “4” represents the value A.sub.1, similar to the case shown in FIG. 26. The pointer 2514 is rotated 90° by the addition of the phase offset (i.e., (p/m)16)=4 for Phase 1, as can be seen in EQ. 33 above, and illustrated by arrow 2702, resulting in a pointer 2704 at position “5”.

(112) A further 90° clockwise rotation representing the addition of b, is shown by the arrow 2706, resulting in the pointer 2708 at position “6”. The value 2.sup.L−1 s then added, as shown by the arrow 2710, resulting in a further 180° clockwise rotation of the pointer 2708, resulting in the pointer 2712 at position “7”, representing a value of 16. Since the sum of EQ. 35 represented by the pointer 2712 is equal to 16 (i.e., 2.sup.L), Bit 1, n.sub.1,1 of Phase 1 will be set to “1” (STEP 1909). That is, since the pointer 2514 representing the value A.sub.1 rotated up to the top of the vector circle 2000 when rotating in response to the sum Mod 16 (A.sub.i+(p/m)16)+b+2.sup.L−1 in STEP 1907, the bit is set to “1”.

(113) Generation of Bit 1, n.sub.2,1 of Phase 2

(114) FIG. 28 is a graphical illustration of the process performed in STEP 1907 for a phase index value p=2 and a bit index value i=1.
Mod 16(A/+(p/m)2.sup.L)+b+2.sup.L−1=  EQ. 36
Mod 16(0+(2/4)16)+4+8=  EQ. 37
Mod 16(0+8)+4+8=  EQ. 38
8+4+8=20  EQ. 39

(115) As noted above, the value A.sub.1 of the accumulator A remains equal to 0 represented by the pointer 2514 at position “4”. The pointer 2514 is rotated clockwise 180° by the addition of the phase offset (i.e., (p/m)16)=8 for Phase 2, as can be seen in EQ. 37 above, and illustrated by arrow 2802, resulting in a pointer 2804 at position “5”.

(116) A further 90° clockwise rotation representing the addition of b, is shown by the arrow 2806, resulting in the pointer 2808 at position “6”. The value 2.sup.L−1 is then added, by a further 180° clockwise rotation of the pointer 2808, as shown by the arrow 2810, resulting in the pointer 2812 at position “7”, representing a value of 20. Since the sum of EQ. 49 represented by the pointer 2812 is greater than 16 (i.e., 2.sup.L), Bit 1, n.sub.2,1 of Phase 2 will be set to “1”. That is, since the pointer 2514 representing the value A.sub.1 rotated past the top of the vector circle 2000 when rotating in response to the sum Mod 16 (A.sub.1+(p/m)16)+b+2.sup.L−1 in STEP 1907, the bit n.sub.2,1 is set to “1”.

(117) Generation of Bit 1, n.sub.3,1 of Phase 3

(118) FIG. 29 is a graphical illustration of the process performed in STEP 1907 for a phase index value p=3 and a bit index value i=1.
Mod 16(A.sub.1+(p/m)2.sup.L)+b+2.sup.L−1=  EQ. 40
Mod 16(0+(3/4)16)+4+8=  EQ. 41
Mod 16(0+12)+4+8=  EQ. 42
12+4+8=24  EQ. 43

(119) As noted above, the value A.sub.1 of the accumulator A remains equal to 0 represented by the pointer 2514 at position “4”. The pointer 2514 is rotated clockwise 270° by the addition of the phase offset (i.e., (p/m)16)=12 for Phase 3, as can be seen in EQ. 41 above, and illustrated by arrow 2902, resulting in a pointer 2904 at position “5”.

(120) A further 90° clockwise rotation representing the addition of b, is shown by the arrow 2906, resulting in the pointer 2908 at position “6”. The value 2.sup.L−1 is then added, by a further 180° clockwise rotation of the pointer 2908, as shown by the arrow 2910, resulting in the pointer 2912 at position “7”, representing a value of 24. Since the sum of EQ. 43 represented by the pointer 2912 is greater than 16 (i.e., 2.sup.L), Bit 1, n.sub.3,1 of Phase 3 will be set to “1”. That is, since the pointer 2514 representing the value A.sub.1 rotated past the top of the vector circle 2000 when rotating in response to the sum Mod 16 (A.sub.1+(p/m)16)+b+2.sup.L−1 in STEP 1907, the bit n.sub.3,1 is set to “1” (STEP 1909).

(121) Next the value of p is incremented to a value of p=4 (STEP 1913). Accordingly, the comparison of STEP 1915 is true, indicating that Bit 1 has been set for all four phases. Therefore, the bit index i is incremented to i=2 and the phase index p is reset to p=0 (STEP 1917). The comparison in STEP 1919 is false, indicating that there are still more bits to be set, since the value of i has not yet reached 2.sup.L.

(122) Generation of Bit 2 (the Third Bit)

(123) FIG. 30 illustrates the update of the accumulator A from A.sub.1 to A.sub.2 as performed by STEP 1921 upon incrementing the bit index i to 2. The update of the accumulators is shown in EQ. 44.
A.sub.2=A.sub.1+b+2.sup.L−1  EQ. 44

(124) In this step, the value of the accumulator is updated by adding the value b as shown by the arrow 3007 illustrating a 90° clockwise rotation of the pointer 2514 at position “4” (representing the previous value A.sub.1 of the accumulator), resulting in the pointer 3008 at position “5” and adding the value 2.sup.L−1, as illustrated by the arrow 3009 showing the pointer 3008 at position “5” rotating to pointer 3010 at position “6” representing the new value A.sub.2=12 of the accumulator A.

(125) Generation of Bit 2, n.sub.0,2 of Phase 0

(126) FIG. 31 is a graphical illustration of the process performed in STEP 1907 for a phase index value p=0 and a bit index value i=2.
Mod 16(A.sub.2+(p/m)2.sup.L)+b+2.sup.L−1=  EQ. 45
Mod 16(12+(0/4)16)+4+8=  EQ. 46
Mod 16(12+0)+4+8=  EQ. 47
12+4+8=24  EQ. 48

(127) A pointer 3010 at position “3” highlighted in red, represents the value A.sub.2. The pointer 3010 is rotated 90° clockwise by the addition of b, as shown by the arrow 3102, resulting in the pointer 3104 at position “4”. The value 2.sup.L−1 is then added, as shown by the arrow 3106, resulting in a further 180° rotation of the pointer 3104, resulting in the pointer 3108 at position “5”, representing a value of 24. Since the sum of EQ. 48 represented by the pointer 3108 is greater than 16 (i.e., 2.sup.L), Bit 2, n.sub.0,2 of Phase 0 will be set to “1”. That is, since the pointer 3110 representing the value A.sub.2 rotated past the top of the vector circle 2000 when summed with b+2.sup.L−1 in STEP 1907, the bit n.sub.0,2 is set to “1”.

(128) Generation of Bit 2, n.sub.1,2 of Phase 1

(129) FIG. 32 is a graphical illustration of the process performed in STEP 1907 for a phase index value p=1 and a bit index value i=2.
Mod 16(A.sub.2+(p/m)2.sup.L)+b+2.sup.L−1  EQ. 47
Mod 16(12+(1/4)16)+4+8=  EQ. 48
Mod 16(12+4)+4+8=  EQ. 49
0+4+8=12  EQ. 50

(130) As noted above, the value A.sub.2 of the accumulator A is 12 and remains the same for each phase until the bit index i is once again incremented in STEP 1917 (i.e., upon the third bit of each phase being set). The pointer 3010 at position “3” represents the value A.sub.2, similar to FIG. 30. The pointer 3010 is rotated clockwise 90° by the addition of the phase offset (i.e., (p/m)16)=4 for Phase 1, as can be seen in EQ. 48 above, and illustrated by arrow 3202, resulting in a pointer 3204 at position “4” representing a value of 16. As can be seen from EQ. 49 and EQ. 50, the modulo 16 operator will cause a 360° counter-clockwise rotation of the pointer 3204 as illustrated by arrow 3205, resulting in a pointer 3206 at position “5” representing a value of 0.

(131) A further 90° clockwise rotation representing the addition of b, is shown by the arrow 3207, resulting in the pointer 3208 at position “6”. The value 2.sup.L−1 is then added, as shown by the arrow 3210, resulting in a further 180° clockwise rotation resulting in the pointer 3212 at position “7”, representing a value of 12. Since the sum of EQ. 50 represented by the pointer 3212 is less than 16 (i.e., 2.sup.L), Bit 2, n.sub.1,2 of Phase 1 will be set to “0”. That is, since the pointer 3204 representing the value A.sub.2 plus the phase offset did not rotate past the top of the vector circle 2000 when rotating in response to the sum Mod 16 (A.sub.2+(p/m)16)+b+2.sup.L−1 in STEP 1907, the bit is set to “0”. It should be noted that the rotation caused by the offset ((p/m)16) is not included when determining whether the advance of the pointer caused the pointer to reach the top of the vector circle 2000. That is, it is only the rotation that occurs after the addition of the phase offset that determines whether the bit is set to a “1” or a “0”.

(132) Generation of Bit 2, n.sub.2,2 of Phase 2

(133) FIG. 33 is a graphical illustration of the process performed in STEP 1907 for a phase index value p=2 and a bit index value i=2.
Mod 16(A.sub.2+(p/m)2.sup.L)+b+2.sup.L−1=  EQ. 51
Mod 16(12+(2/4)16)+4+8=  EQ. 52
Mod 16(12+8)+4+8=  EQ. 53
4+4+8=16  EQ. 54

(134) As noted above, the value A.sub.2 of the accumulator A remains equal to 12 and the pointer 3010 at position “3” represents the value A.sub.2=12 The pointer 3010 is rotated clockwise 90° by the addition of the phase offset (i.e., (p/m)16)=4 for Phase 2, as can be seen in EQ. 52 above, and illustrated by arrow 3202, resulting in a pointer 3204 at position “4”. Since the sum within the modulo 16 operator is equal to 20, the value after performing the modulo 16 operation is 4. Arrow 3305 illustrates the sum of A.sub.2 with the phase offset being set to 4 by the modulo 16 operation, resulting in a pointer 3306 at position “5”.

(135) A 90° clockwise rotation representing the addition of b, is shown by the arrow 3307, resulting in the pointer 3308 at position “6” representing a value of 8. The value 2.sup.L−1 is then added, resulting in a further 180° clockwise rotation as shown by the arrow 3310, resulting in the pointer 3312 at position “7”, representing a value of 16. Since the sum of EQ. 54 represented by the pointer 3212 is equal to 16 (i.e., 2.sup.L), Bit 2, n.sub.2,2 of Phase 2 will be set to “1”. That is, since the pointer 3306 representing the value A.sub.2 plus the phase offset rotated up to the top of the vector circle 2000 when rotating in response to the sum Mod 16 (A.sub.2+(p/m)16)+b+2.sup.L−1 in STEP 1907, the bit is set to

(136) Generation of Bit 2, n.sub.3,2 of Phase 3

(137) FIG. 34 is a graphical illustration of the process performed in STEP 1907 for a phase index value p=3 and a bit index value i=2.
Mod 16(A.sub.2+(p/m)2.sup.L)+b+2.sup.L−1=  EQ. 55
Mod 16(12+(3/4)16)+4+8=  EQ. 56
Mod 16(12+12)+4+8=  EQ. 57
8+4+8=20  EQ. 58

(138) As noted above, the value A.sub.2 of the accumulator A remains equal to 12 represented by the pointer 3010 at position “3”. The pointer 3010 is rotated clockwise 270° by the addition of the phase offset (i.e., (p/m)16)=12 for Phase 3, as can be seen in EQ. 57 above, and illustrated by arrow 3402, resulting in a pointer 3404 at position “4” representing a value of 24. However, because the sum of A.sub.2 plus the phase offset is operated on by the modulo 16 operator, the pointer 3404 is rotated 360° counter-clockwise, as illustrated by arrow 3405, resulting in the pointer 3406 at position “5”.

(139) A further 90° clockwise rotation representing the addition of b, is shown by the arrow 3407, resulting in the pointer 3408 at position “6” representing a value of 12. The value 2.sup.L−1 is then added, causing a further 180° clockwise rotation of the pointer 3408, illustrated by the arrow 3410, resulting in the pointer 3412 at position “7”, representing a value of 20. Since the sum of EQ. 58 represented by the pointer 3412 is greater than 16 (i.e., 2.sup.L), Bit 2, n.sub.3,2 of Phase 3 will be set to “1”. That is, since the pointer 3404 (highlighted in red) representing the value A.sub.2 plus the phase offset rotated past the top of the vector circle 2000 when rotating in response to the sum Mod 16 (A.sub.2+(p/m)16)+b+2.sup.L−1 in STEP 1907, the bit n.sub.3,2 is set to “1” (STEP 1909).

(140) Next the value of p is incremented to a value of p=4 (STEP 1913). Accordingly, the comparison of STEP 1915 is true, indicating that Bit 2 has been set for all four phases. Therefore, the bit index i is incremented to i=3 and the phase index p is reset to p=0 (STEP 1917). The comparison in STEP 1919 is false, indicating that there are still more bits to be set, since the value of i has not yet reached 2.sup.L.

(141) Generation of “Bit 3” (i.e., the Fourth Bit)

(142) FIG. 35 illustrates the update of the value A.sub.i stored in the accumulator from A.sub.2 to A.sub.3 (STEP 1921 and STEP 1905). EQ. 24 through EQ. 27 below show the calculation of A.sub.3:
A.sub.3=A.sub.2+b+2.sup.L−1  EQ. 59
A.sub.3=12+4+8=24  EQ. 60
A.sub.3=A.sub.3−2.sup.L=  EQ. 61
A.sub.3=24−16=8  EQ. 62

(143) The value b is added to A.sub.2, as indicated by the arrow 3507 illustrating the rotation of the pointer 3010 from position “1” representing a value of 12, to position “2” of the pointer 3508 representing a value of 16. 2.sup.L−1 is then added, as illustrated by the arrow 3509 showing the pointer 3508 at position “2” rotating 180° clockwise to pointer 3510 at position “3”. In some embodiments, the value A.sub.i stored in the accumulator should remain in the range of 0 to 2.sup.L−1 (i.e., between 0 and 15 in the example shown). Accordingly, if the value A.sub.3 is equal or greater than 2.sup.L (STEP 1903), it is reduced by 2.sup.L (STEP 1905). Accordingly, the pointer 3510 at position “3” representing a value of 24 is rotated counter-clockwise by 360°, as indicated by arrow 3512, resulting in the pointer 3514 at position “4” (STEP 1905) representing a value of 8, as indicated by EQ. 62.

(144) Generation of “Bit 3”, n.sub.0,3 of Phase 0

(145) FIG. 36 is a graphical illustration of the process performed in STEP 1907 for a phase index value p=0 and a bit index value i=3.
Mod 16(A.sub.3+(p/m)2.sup.L)+b+2.sup.L−1  EQ. 63
Mod 16(8+(0/4)16)+4+8=  EQ. 64
Mod 16(8+0)+4+8=  EQ. 65
8+4+8=20  EQ. 66

(146) The value A.sub.3 can be seen from EQ. 62 to be equal to 8. A pointer 3514 at position “4” represents the value A.sub.3. The pointer 3514 is rotated 90° clockwise by the addition of b, as illustrated by the arrow 3602, resulting in the pointer 3604 at position “5”. The value 2.sup.L−1 is then added, resulting in a further 180° rotation of the pointer 3604, as illustrated by the arrow 3606 and resulting in the pointer 3608 at position “6” representing a value of 20. Since the sum of EQ. 66 represented by the pointer 3608 is greater than 16 (i.e., 2.sup.L), Bit 3, n.sub.0,3 of Phase 0 will be set to “1”. That is, since the pointer 5514 representing the value A.sub.3 plus the phase offset rotates past the top of the vector circle 2000 when summed with b+2.sup.L−1 in STEP 1907, the bit is set to “1”.

(147) Generation of Bit 3, n.sub.1,3 of Phase 1

(148) FIG. 37 is a graphical illustration of the process performed in STEP 1907 for a phase index value p=1 and a bit index value i=1 for generating Bit 1 of Phase 1. EQ. 67 through EQ. 70 show the details of the calculation performed in STEP 1907.
Mod 16(A.sub.3+(p/m)2.sup.L)+b+2.sup.L−1  EQ. 67
Mod 16(8+(1/4)16)+4+8=  EQ. 68
Mod 16(8+4)+4+8=  EQ. 69
12+4+8=24  EQ. 70

(149) As noted above in EQ. 68, the value A.sub.3=8 and remains the same for each phase until the bit index i is incremented in STEP 1917 (i.e., upon all of the second bits of each phase being set). The pointer 3514 at position “4” represents the value A.sub.3, similar to the case shown in FIG. 36. The pointer 3514 is rotated 90° by the addition of the phase offset (i.e., (p/m)16)=12 for Phase 1, as can be seen in EQ. 70 above, and illustrated by arrow 3702, resulting in a pointer 3704 at position “5”.

(150) A further 90° clockwise rotation representing the addition of b, is shown by the arrow 3706, resulting in the pointer 3708 at position “6”. The value 2.sup.L−1 is then added, as illustrated by the arrow 3710, resulting in a further 180° clockwise rotation of the pointer 3708, resulting in the pointer 3712 at position “7”, representing a value of 24. Since the sum of EQ. 70 represented by the pointer 3712 is greater than 16 (i.e., 2.sup.L), Bit 3, n.sub.1,3 of Phase 1 will be set to “1” (STEP 1909). That is, since the pointer 3704 representing the value A.sub.1 plus the phase offset rotated past the top of the vector circle 2000 when rotating in response to the sum Mod 16 (A.sub.3+(p/m)16)+b+2.sup.L−1 in STEP 1907, the bit is set to “1”.

(151) Generation of Bit 3, n.sub.2,3 of Phase 2

(152) FIG. 38 is a graphical illustration of the process performed in STEP 1907 for a phase index value p=2 and a bit index value i=3.
Mod 16(A.sub.3+(p/m)2.sup.L)+b+2.sup.L−1=  EQ. 71
Mod 16(8+(2/4)16)+4+8=  EQ. 72
Mod 16(8+8)+4+8=  EQ. 73
0+4+8=12  EQ. 74

(153) As noted above, the value A.sub.3 of the accumulator A remains equal to 8 represented by the pointer 3514 at position “4”. The pointer 3514 is rotated clockwise 180° by the addition of the phase offset (i.e., (p/m)16)=8 for Phase 2, as can be seen in EQ. 72 above, and illustrated by arrow 3802, resulting in a pointer 3804 at position “5”.

(154) A further 90° clockwise rotation representing the addition of b, is shown by the arrow 3806, resulting in the pointer 3808 at position “6”. The value 2.sup.L−1 is then added, by a further 180° clockwise rotation of the pointer 3808, as shown by the arrow 3810, resulting in the pointer 3812 at position “7”, representing a value of 20. Since the sum of EQ. 74 represented by the pointer 3812 is less than 16 (i.e., 2.sup.L), Bit 3, n.sub.2,3 of Phase 2 will be set to “0”. That is, since the pointer 3514 representing the value A.sub.3 plus the phase offset did not rotate up to the top of the vector circle 2000 when rotating in response to the sum Mod 16 (A.sub.3+(p/m)16)+b+2.sup.L−1 in STEP 1907, the bit n.sub.2,3 is set to “0”.

(155) Generation of Bit 3, n.sub.3,3 of Phase 3

(156) FIG. 39 is a graphical illustration of the process performed in STEP 1907 for a phase index value p=3 and a bit index value i=3.
Mod 16(A.sub.3+(p/m)2.sup.L)+b+2L.sup.−1=  EQ. 75
Mod 16(8+(3/4)16)+4+8=  EQ. 76
Mod 16(8+12)+4+8=  EQ. 77
4+4+8=16  EQ. 78

(157) As noted above, the value A.sub.3 of the accumulator A remains equal to 8 represented by the pointer 3514 at position “4”. The pointer 3514 is rotated clockwise 270° by the addition of the phase offset (i.e., (p/m)16)=12 for Phase 3, as can be seen in EQ. 78 above, and illustrated by arrow 3902, resulting in a pointer 3904 at position “5” representing a value of 20. The modulo 16 operator results in a counter-clockwise rotation of 360°, as illustrated by arrow 3905 and resulting in a pointer 3906 at position “6” representing a value of 4.

(158) A further 90° clockwise rotation representing the addition of b, is shown by the arrow 3907, resulting in the pointer 3908 at position “7”. The value 2.sup.L−1 is then added, by a further 180° clockwise rotation of the pointer 3908, as shown by the arrow 3910, resulting in the pointer 3912 at position “8”, representing a value of 16. Since the sum of EQ. 78 represented by the pointer 3912 is equal to 16 (i.e., 2.sup.L), Bit 3, n.sub.3,3 of Phase 3 will be set to “1”. That is, since the pointer 3906 representing the value A.sub.3 plus the phase offset rotated up to the top of the vector circle 2000 when rotating in response to the sum Mod 16 (A.sub.3+(p/m)16)+b+2.sup.L−1 in STEP 1907, the bit n.sub.3,3 is set to “1” (STEP 1909).

(159) Next the value of p is incremented to a value of p=4 (STEP 1913). Accordingly, the comparison of STEP 1915 is true, indicating that Bit 3 has been set for all four phases. Therefore, the bit index i is incremented to i=4 and the phase index p is reset to p=0 (STEP 1917). The comparison in STEP 1919 is still false, indicating that there are more bits to be set, since the value of i is not yet equal to 2.sup.L.

(160) Therefore, the value of the accumulator A is updated (STEP 1921) to:
A.sub.4=A.sub.3+b+2.sup.L−1=  EQ. 79
A.sub.4=8+4+8=20  EQ. 80
A.sub.4=A.sub.4−16=4  EQ. 81

(161) The sum of EQ. 79 is calculated in STEP 1921. Then the value of the accumulator A is checked to see whether it is equal to or greater than 2.sup.L (i.e., 16). Since the result of the compare (STEP 1903) is true, the value of the accumulator A is reduced (STEP 1905) before performing the calculation and compare in STEP 1907.

(162) It will be seen that the value of the accumulator A.sub.4 is the same as the previously calculated value A.sub.o. Since all of the other variables (p, m, L, b) in the comparison of STEP 1907 are the same as they were when the value of the bit index was i=0, the process will start to repeat itself. That is, the state of bit 5 of each phase will be the same as the state of bit 0 for each phase. For example, the bit n.sub.0,0 will be in the same state as the bit n.sub.0,4. Similarly, bit n.sub.0,1 will be in the same state as bit n.sub.0,5.

(163) FIG. 40 shows the value of each of the bits from i=0 to i=15 for each of the four sequences generated in each phase (p=1 through p=3). It should be noted that the pattern of bits in each sequence repeats in a four-bit pattern in response to the value b=4. For other values of b, the pattern repeats with a different period. For example, if b=0, the pattern repeats with a period of 2 bits rather than 4 bits. However, in each case, the ones and zeros will be evenly distributed throughout each sequence, with the placement of the bits shifted in phase from one sequence to the next. That is, the sequence for N.sub.0 is shifted one bit to the left with respect to the sequence for N.sub.1, which is shifted one bit to the left with respect to the sequence for N.sub.2, which is shifted on bit to the left with respect to the sequence N.sub.3, which is shifted one bit to the left with respect to the sequence of N.sub.0. Note that when each sequence is shifted, the bit at n.sub.p,0 is shifted to bit n.sub.p,15.

(164) Table 1 below shows the values for the accumulator for each bit index i. It can be seen from Table 1 and from STEP 1921, STEP 1903 and STEP 1905 that the value A.sub.i of the accumulator A is incremented at each increment of the bit index i by A.sub.i=Mod 16(A.sub.i−1+b+2.sup.L−1). Table 1 also shows that the value repeats every four increments of the bit index i (i.e., every four bits).

(165) TABLE-US-00001 TABLE 1 A.sub.0 4 A.sub.1 0 A.sub.2 12 A.sub.3 8 A.sub.4 4 A.sub.5 0 A.sub.6 12 A.sub.7 8 A.sub.8 4 A.sub.9 0 A.sub.10 12 A.sub.11 8 A.sub.12 4 A.sub.13 0 A.sub.14 12 A.sub.15 8

(166) FIG. 41 is a simplified schematic of one embodiment for implementing the multiphase δ-sequence generator described above. A multiplexer 4102 selects between two inputs (“X” and “Y”) based on the state of a select signal. The select signal is generated by a comparator 4104. The comparator 4104 outputs a logical “1” when the value of the phase index p and the bit index i are both equal to zero. The phase index p is maintained in a phase index counter 4106. In some embodiments, the phase index counter is a register that roles over to zero on the next count after p=m−1. That is, the phase index counter 4106 has a range from 0 to m−1. The bit index is maintained in a bit index counter 4108. In some embodiments, the bit index counter 4108 roles over to zero on the next count after i=2.sup.L−1. Accordingly, the bit index counter has a range from 0 to 2.sup.L−1.

(167) In some embodiments, the phase index counter 4106 and the bit index counter 4108 are provided a hard reset to zero when the circuit is initialized. Accordingly, upon initialization, the select signal will be a logic “1”. When the select signal is a logic “1”, the multiplexer 4102 selects the X input. The X input is coupled to a summing circuit 4110. The summing circuit 4110 has two inputs. The first input is coupled to a register 4112 that holds the value of b. The second input is coupled to a register 4114 that holds the value of 2.sup.L. The summing circuit outputs the sum of the values coupled to the two inputs, b and 2.sup.L. The selected output from the multiplexer 4102 is coupled to an accumulator 4116. The accumulator 4116 holds each value until the value of the bit index i changes. The particular input used to cause the accumulator to store the next value is not shown, but those of ordinary skill will understand how to generate the input.

(168) With the value 2.sup.L+b stored in the accumulator 4116, the output of the accumulator 4116 is coupled to three different devices. The first device is a multiplexer 4118. The output of the accumulator is coupled to the first input of the multiplexer 4118. The second device is a comparator 4120. The output of the accumulator is coupled to the non-inverting input to the comparator 4120. The third device is subtraction circuit 4122. The output of the accumulator is coupled to one of two inputs to the subtraction circuit. The second input to the subtraction circuit 4122 and the inverting input to the comparator 4120 are coupled to the output of the register 4114 that holds the value 2.sup.L. The output of the subtraction circuit 4122 is coupled to the second input to the multiplexer 4118. The output of the comparator 4120 is coupled to the select input of the multiplexer 4118. Therefore, when the 2.sup.L is equal to or greater than the value stored in the accumulator 4116, the comparator will output a logical “1”, causing the multiplexer to select the Y input that is coupled to the subtraction circuit 4122. The selected input is coupled to the output of the multiplexer 4118. Accordingly, the output of the multiplexer will be equal to the value of the accumulator minus 2.sup.L. Alternatively, if the value in the accumulator 4116 is less than the 2.sup.L, the multiplexer will select the X input and the output of the multiplexer will be equal to the value stored in the accumulator 4116. Accordingly, the circuitry described thus far performs the STEPs 1901 through 1905 shown in FIG. 19.

(169) The output of the multiplexer 4118 is coupled to a first input to a summing circuit 4124. The summing circuit 4124 outputs the sum Mod2.sup.L(A.sub.i+(p/m)2.sup.L). The value (p/m)2.sup.L is provided to the second input to the summing circuit 4124 by a register 4126. The output of the register 4126 is coupled to the second input to the summing circuit 4124. In some embodiments, the register 4126 is a look up table that is addressed by the values of the phase index p and the terminal value of the phase index m and potentially the value 2.sup.L. The terminal value m is provided to the the register 4126 by a register 4128 that holds the value m. The output of the phase index counter 4106 provides the value of the phase index p. In addition, the output of the 4114 is coupled to the register 4126 to provide the value 2.sup.L.

(170) The output Mod2.sup.L(A.sub.i+(p/m)2.sup.L) of the summing circuit 4124 is coupled to another summing circuit 4130. The summing circuit 4130 adds the values b and 2L.sup.1 to Mod2.sup.L(A.sub.i+(p/m)2.sup.L). This sum is then coupled from the output of the summing circuit 4130 to the non-inverting input of a comparator 4132. The inverting input to the comparator 4132 is coupled to the register 4114 that holds the value 2.sup.L. Accordingly, the comparator 4132 outputs a logical “1” if the output of the summing circuit 4130 is greater than or equal to 2.sup.L and a logical “0” if not. It can be seen that the output of the comparator performs the function that is noted in STEPs 1907, 1909 and 1911 of FIG. 19. The particular bit at issue is set by storing the output of the comparator 4132 at an address in a memory device 4134 that is determined by the values of the phase index p and the bit index i. Upon storing the bit in the memory 4134, a clock 4136 coupled to the phase index counter 4106 increments the value of the phase index counter 4106. A comparator 4138 checks whether the phase index counter 4106 has rolled over to zero. If so, the comparator 4138 output a reset signal to cause the value of the bit index counter 4108 to increment and the phase index counter 4106 to reset.

(171) It should be clear that each time the clock 4136 increments the value of the phase index counter 4106, a new value will be determined at the output of the summing circuit 4130 and a determination will be made as to whether the particular bit n.sub.p,i associated with the values of the phase and bit index counters is to be a “1” or a “0”. The i.sup.th bit of each of the N.sub.p sequences will in turn be stored until the phase index counter 4106 rolls over to zero indicating that all of the i.sup.th bits of each phase have been set, at which time the bit index counter 4108 will increment. The first time the bit index counter increments, a signal is generated to cause the accumulator 4116 to store the value that is provided at the input of the accumulator 4116. Since the bit index i is no longer zero at that time, the select signal to the multiplexer 4102 will cause the multiplexer 4102 to select the Y input, which is coupled to a summing circuit 4140. The summing circuit 4140 has three inputs, the first coupled to the output of the register that holds the value b. The second is coupled to the output of a shift register 4142. The shift register 4142 is coupled to the register that holds that value 2.sup.L. The shift register generates the value 2.sup.L−1 by performing a single shift right on the value 2.sup.L. The third input to the summing circuit 4140 is coupled to the output of the multiplexer 4118. Accordingly, the summing circuit 4140 outputs the sum A.sub.i=A.sub.i−1+b+2.sup.L−1, as shown in STEP 1921 of FIG. 19, which is coupled by the multiplexer 4102 to the input of the accumulator. The output of the accumulator 4116 is then compared to 2.sup.L in the comparator 4120. If equal or greater than 2.sup.L, subtraction circuit 4122 reduces the value by 2.sup.L. The new value of output from the multiplexer 4118 is then used to determine whether the next bit of each phase is to be set to a “1” or a “0”. If the bit index counter 4108 rolls over to zero, the process will start again. In some embodiments, as shown in FIG. 19, a comparator can be used to determine when to end the process.

(172) FIG. 42 is a simplified schematic illustrating single node 4200 of a neural network within an artificial intelligence engine. The node 1400 consists of two multiplier circuits 4202, 4204 and a summing circuit 4206. The node 4200 receives four inputs, input signal 1, input signal 2, weight W1 and weight W2. Input signal 1 and input signal 2 are signals that represent an input values X and Y, respectively. Weights W1 and W2 are signals that represent weight values w1 and w2, respectively that are used to modify the input values X and Y, respectively. Input 1 and the weight W1 are coupled to the inputs of the multiplier circuit 4202. A signal representing the produce of X (i.e., the value represented by input signal 1) and w1 (i.e., the value represented by weight W1) is provided at the output of the multiplier circuit 4202. Similarly, input 2 and the weight W2 are coupled to the inputs of the multiplier circuit 4204. A signal representing the produce of the Y (i.e., the value represented by input signal 1) and w1 (i.e., the value represented by the weight W1) is provided at the output of the multiplier circuit 4204.

(173) The output of the multiplier circuit 4202 and the output of the multiplier circuit 4204 are then each coupled to one of the two inputs to the summing circuit 4206. The output of the summing circuit 4206 is coupled to the output of the node 4200. Accordingly, the output of the node 4200 is equal to the sum:
w1(X)+w2(Y).  EQ. 82

(174) FIG. 43 is a simplified schematic of a portion of a neural network (i.e., with only one node 4200 shown) within an artificial intelligence engine 4300. In the embodiment shown in FIG. 43, values to be multiplied at particular nodes (such as node 4200) within the artificial intelligence engine 4300 are stored in binary format and then converted to SBSs prior to being presented to the nodes. Storing the values in binary format allows the value to be stored in a relatively small amount of memory. Converting the values from binary format to SBS format prior to performing the multiplication operation reduces the hardware required to perform multiplication.

(175) A series of SBS generators 4302, 4304, 4306, 4308 perform the conversion. In some embodiments, the SBS generators, 4302, 4304, 4306, 4308 function as described above to convert the binary values represented by the input signals (Binary input 1, Binary input 2, Binary weight 1, Binary weight 2) into SBS sequences represented by the SBS input signals (SBS input 1, SBS input 2, SBS input 3, SBS input 4).

(176) It will be understood that the artificial intelligence engine 4300 is a simplification in which only one neural network node 4200 is shown. However, in other more interesting artificial intelligence engines (not expressly shown) there may be several nodes to which it might be beneficial to provide different phases of a particular binary input or binary weight. In such cases, a multi-phase δ-sequence generator can be used to convert a binary input or binary weight into a plurality of SBS sequences that are each out of phase with one another.

CONCLUSION

(177) A number of embodiments of the disclosed method and apparatus have been described. It is to be understood that various modifications may be made without departing from the spirit and scope of the disclosed method and apparatus. For example, some of the steps described above may be order independent, and thus can be performed in an order different from that described. Further, some of the steps described above may be optional. Various activities described with respect to the methods identified above can be executed in repetitive, serial, or parallel fashion. It is to be understood that the foregoing description is intended to illustrate and not to limit the scope of the any claims that are presented in later filed applications that might claim priority to this disclosure.