Method and apparatus for efficient multiplication to improve performance in computational machines

Abstract

A method and apparatus is disclosed for determining a stochastic binary string (SBS) representing a value based on the value represented in binary two's complement. Several different generators are disclosed for generating SBS strings, each being generated to have particular features that are advantageous under various conditions in which the string is to be multiplied with another SBS string. Several such generators can be presented and selected depending upon the particular values to be converted to SBS representation and the functions to be performed on those values.

Claims

1. A stochastic binary string (SBS) generator, comprising: (a) a plurality of SBS generator sub-blocks, each sub-block generating an SBS sequence using a different technique; (b) a selector for selectively coupling an input value to a selected one from among the plurality of SBS generator sub-blocks; and (c) a processor coupled to the selector to control the selection performed by the selector.

2. The SBS generator of claim 1, wherein the plurality of SBS generator sub-blocks include at least one SBS ρ-sequence generator sub-block that generates ρ-sequence SBS sequences.

3. The SBS generator of claim 1, wherein the plurality of SBS generator sub-blocks include at least one SBS δ-sequence generator sub-block that generates δ-sequence SBS sequences.

4. The SBS generator of claim 1, wherein the plurality of SBS generator sub-blocks include at least one SBS ω-sequence generator sub-block that generates ω-sequence SBS sequences.

5. The SBS generator of claim 1, wherein: (a) the plurality of SBS generator sub-blocks includes a first SBS ρ-sequence generator sub-block generates SBS ρ-sequence strings; (b) the plurality of SBS generator sub-blocks includes a second SBS δ-sequence generator sub-block that generates SBS δ-sequence strings; (c) the processor selects from among the plurality of SBS generator sub-blocks, the first SBS generator sub-block to generate a first SBS sequence; and (d) the processor selects from among the plurality of SBS generator sub-blocks, the second SBS generator sub-block to generate a second SBS sequence to be multiplied with the first SBS sequence.

6. The SBS generator of claim 5, further including at least one exclusive nor (XNOR) gate having a first input coupled to the first SBS generator sub-block to receive the first SBS sequence and having a second input coupled to the second SBS generator sub-block to receive the second SBS sequence, the output of the XNOR gate being the product of the first SBS sequence and the second SBS sequence.

7. The SBS generator of claim 1, wherein the plurality of SBS generator sub-blocks include at least one SBS generator sub-block that generates SBS sequences using a σ-sequence method.

8. The SBS generator of claim 7, wherein the plurality of SBS generator sub-blocks include at least one SBS generator sub-block that generates SBS sequences using a δ-sequence method.

9. The SBS generator of claim 7, wherein the plurality of SBS generator sub-blocks include at least one SBS generator sub-block that generates SBS sequences using a ω-sequence method.

10. The SBS generator of claim 7, wherein: (a) the plurality of SBS generator sub-blocks includes a first SBS generator sub-block that generates SBS sequences using a σ-sequence method; (b) the plurality of SBS generator sub-blocks includes a second SBS generator sub-block that generates SBS sequences using a δ-sequence method; (c) the processor selects from among the plurality of SBS generator sub-block, the first SBS generator sub-block to generate a first SBS sequence; and (d) the processor selects from among the plurality of SBS generator sub-blocks, the second SBS generator sub-block to generate a second SBS sequence to be multiplied with the first SBS sequence.

11. The SBS generator of claim 10, further including at least one exclusive nor (XNOR) gate having a first input coupled to the first SBS generator sub-block to receive the first SBS sequence and having a second input coupled to the second SBS generator sub-block to receive the second SBS sequence, the output of the XNOR gate being the product of the first SBS sequence and the second SBS sequence.

12. The SBS generator of claim 1, wherein the plurality of SBS generator sub-blocks include at a first SBS generator sub-block, wherein the first SBS generator sub-block generates SBS sequences using ζ-sequence method.

13. The SBS generator of claim 12, wherein the processor selects from among the plurality of SBS generator sub-blocks the first SBS generator sub-block when an SBS sequence generated by one of the other SBS generator sub-blocks is to be multiplied by zero and wherein the first SBS generator outputs an SBS sequence of zero.

Description

DESCRIPTION OF THE DRAWINGS

(1) FIG. 1a through FIG. 1c illustrate an “ideal” bipolar SBS 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. 3a is an illustration of two USBS sequences that are completely correlated.

(4) FIG. 3b is an illustration of two USBS sequences that are completely uncorrelated.

(5) FIG. 4 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. 5 is an illustration of an XNOR gate used to multiply two BSBS sequences.

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

(8) FIG. 6b is an illustration of a case in which the two strings representing values of 0 are completely anticorrelated.

(9) FIG. 7 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. 8 is an illustration of a generator that generates ω-sequences.

(11) FIG. 9 is an illustration of a more generalized ω-sequence generator in which T is not equal to 2.sup.L.

(12) 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.

(13) FIG. 11 provides a graphic representation of steps shown in the flowchart of FIG. 10.

(14) FIG. 12 is a graphical representation of the value A.sub.i for i=0.

(15) FIG. 13 is a graphical representation of the value of the accumulator A after STEP 1009 of FIG. 10 has been performed.

(16) FIG. 14 is a graphical representation showing the value of the accumulator A after the index, i has been incremented to 2.

(17) FIG. 15 is a graphical representation showing the value of the accumulator A after the next pass through STEP 1009, in which the index is incremented to i=3.

(18) FIG. 16 is a graphical representation showing the value of the accumulator A after the next pass through STEP 1009, in which the index is incremented to i=4.

(19) FIG. 17 is a graphical representation showing the value of the accumulator A after the index, i has been incremented to the terminal value.

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

(21) FIG. 19 is a flowchart of the steps performed by a δ-sequence generator to generate a USBS sequence.

(22) FIG. 20 is a flowchart of an algorithm that is used in some embodiments to generate a σ-sequence.

(23) FIG. 21 is an illustration of an example of a circuit for implementing a σ-sequence generator.

(24) FIG. 22 is a flowchart of the method used to generate a ζ-sequence.

(25) FIG. 23 is a simplified illustration of one embodiment for implementing a ζ-sequence generator.

(26) FIG. 24 is an alternative embodiment for implementing a ζ-sequence generator for generating sequences of ζ(r,s)=ζ(1,0).

(27) FIG. 25 is a simplified schematic of ζ(r,s)=ζ(2,0) generator.

(28) FIG. 26 is a simplified schematic of ζ(r,s)=ζ(2,1) generator.

(29) FIG. 27 is a simplified schematic of ζ(r,s)=ζ(3,2) generator.

(30) FIG. 28 is a simplified schematic of ζ(r,s)=ζ(3,1) generator.

(31) FIG. 29 is a simplified block diagram of a generator comprising a plurality of SBS generator sub-blocks generating sequences by different techniques.

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

DETAILED DESCRIPTION

(33) 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.

(34) One such SBS generator generates an ω-sequence. An ω-sequence is a string that presents a numerical value in SBS format. An ω-sequence may be either a binary SBS (BSBS) or a unipolar SBS (USBS). The ω-sequence may be used either once or repeated multiple times within an SBS sequence. Within each ω-sequence, the number of transitions from “1” to “0” is minimized by grouping the 1-bits together and grouping the 0-bits together. Accordingly, the output of an ω-sequence generator is a string of is followed by a string of 0s. The number of ones in the first part of the string will be equal to pT, the product of the probability associated with each bit of the SBS sequence N and the length T of the SBS sequence. In general, the probability p that a bit of a BSBS sequence is assigned a value of “1” is determined as a function of a value n being represented by the SBS sequence. For a BSBS, the probability p=(c+n)/2c, and the BSBS sequence N can represent values n in a range from −c to c. For a USBS, the probability is p=n/c. and the sequence N can represent values n in a range from f to c, where f≤n≤c.

(35) Conversion of a value b represented in binary form to a value n represented by an either a USBS or a BSBS sequence N using an ω-sequence can be performed as follows. For a USBS sequence, the probability is p=c/n, where c is the ceiling (i.e., largest number that can be represented by the USBS). For a BSBS, the probability p can be expressed as (2.sup.L−1+b)/2.sup.L, where L is bit precision in the binary representation and b is the value represented in binary form. The bit precision of the binary representation is the length of the binary number (i.e., number of bits) used to represent the value. The probability p can be used to determine the number of bits that are assigned a value of “1” within the ω-sequence. That is, the number of ones in the ω-sequence is equal to pT. In one embodiment, the value pT is compared to the output of a counter that runs from 0 to T. If the value pT is larger than the output of the counter, a “1” is generated within the ω-sequence; otherwise a zero is generated. Once the counter runs the full range from 0 to T, a complete ω-sequence is generated in which the value b is represented in SBS format as a string of pT bits followed by a string of T(1−p) bits assigned a value of zero. An example is provided below to illustrate this.

(36) FIG. 8 is an illustration of a generator that generates BSBS ω-sequences. A counter 801 provides a series of values that start at zero and increment by one in a sequence to T, where T is the length of the ω-sequence SBS sequence. The output of the counter 801 is coupled to the negative input of a comparator 803. A value b to be represented by the ω-sequence SBS sequence is taken from a source, such as a memory 805, and coupled to the input of a conversion block 807. The conversion block 807 converts the value b to a value that is equal to pT, the probability that a bit of the SBS sequence N will be a assigned a value of “1”, multiplied by the number of bits T in the string N. In accordance with some embodiments:
p=(2.sup.L−1+b)/2.sup.L  EQ. 1
T=2.sup.L  EQ. 2
2.sup.L−1=T/2  EQ. 3
pT=(2.sup.L−1+b)  EQ. 4 where: p is the probability that a bit in the BSBS sequence is assigned a value of “1”; L is the bit precision (i.e., the number of bits in the binary format used to express the magnitude) of the value to be converted from binary format to BSBS format; T is the number of bits in the BSBS sequence; and b expressed in binary format that is to be converted for representation in BSBS format.

(37) Therefore, pT can be generated by summing T/2 with the binary value of b. For example, if the value b is a binary value of “0010” (representing a value of 2), represented in a 4-bit 2s-complement binary representation (a signed binary representation that can hold a value from −8 to 7), then the value of L is 3. For this example, T=2.sup.L=2.sup.3=8; represented in binary form as “01000”. The value of 2.sup.L−1 is 4; “00100” in binary format, which is a simple right shift of T. Adding this binary value to the binary value of b yields b+2.sup.L−1=pT=00110. It should be noted that the bit precision of the register needed to hold the value L must be at least one greater than the bit precision of the register needed to hold the value of b.

(38) By applying b+2.sup.L−1=00110 to the positive input of the comparator 803 and applying the value of i output from the counter 801 to the negative input of the comparator 801, the comparator will output a string in which the first 10 bits are ones and the following 6 bits are zeros (i.e., the desired ω-sequence representing the value 0010 binary as a BSBS sequence N having a length T=16). It can be seen that the ω-sequence generator 800 can generate the w-sequence using only simple addition and comparisons. The bits output from the comparator 803 are coupled to the input of a register 809 and stored under the control of an index, i output from the counter 801. The register outputs the string N having bits n.sub.0−n.sub.T-1.

(39) FIG. 9 is an illustration of a more generalized ω-sequence generator 900 in which T is not equal to 2.sup.L. A second converter block 902 is coupled between the output of the counter 801 and the negative input of the comparator 803 to multiply the output of the counter 801 by 2.sup.L/T. It can be seen that if the length T of the SBS sequence is an integer multiple, for example, of the length 2.sup.L of the binary representation of the value b to be converted, then the values are coupled to the negative input of the comparator 803 will run from 0 to 2.sup.L. In some embodiments, the scaling that is performed in converter block 902 can be performed by a shift of the input i, assuming the value of T is a power of 2. It should also be noted that for the ω-sequence generator 900 to output a complete ω-sequence, T must be greater than L. In accordance with some embodiment, T is an integer multiple of L.

(40) A BSBS sequence generated using a ω-sequence has several properties of interest. The first of these properties is that the maximum relative error for the ω-sequence is less than 1/T. That is, converting a binary value to a SBS sequence, and then converting the SBS sequence back to a binary number will result in an relative error that is less than 1/T, where T is the length of the ω-sequence. Another property of a SBS sequence generated with an ω-sequence is that it can be generated without the use of a random number generator. Yet another property of a SBS that has been generated with an ω-sequence is that the SBS sequence will have the fewest possible transitions (state changes between one and zero). However, an accurate product cannot be obtained when multiplying a SBS sequence that has been generated using a ω-sequence generator with another SBS sequence that has been generated using a ω-sequence. Neither can an accurate product be attained when multiplying a SBS sequence that has been generated using a w-sequence with a time-shifted version of itself.

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

(42) FIG. 10 is a flowchart of an algorithm that is used in some embodiments of the δ-sequence generator to generate a BSBS δ-sequence in which the ones are evenly distributed throughout the δ-sequence. To start, an index counter 1001 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., converted from a two's complement binary representation to BSBS representation). It should be noted that the value 2.sup.L is one greater than the maximum value that can be represented by b, since L is the length (i.e., bit precision) of the unsigned portion (or magnitude) of the binary value b. For example, if b is a 4-bit two's complement binary number, then L=4. It should be noted that a 4-bit two's complement binary number has a bit precision of 3 bits that represent the magnitude of the value and one bit that represents the polarity (i.e., negative or positive) of the value. Accordingly, for a two's complement representation of the value 4, b=0100. Accordingly, for L=4:2.sup.L−1=2.sup.3=8. Therefore, the range of values that can be represented by b is from 1000=−8 to 0111=7. Accordingly, the maximum value that can be represented by b is 7=2.sup.L−1−1=2.sup.3−1. A 4-bit two's complement representation of the value −4 is b=1100. The lead bit indicates that the value represented by the following three bits is negative; in this case the following three bits being 100 indicate the magnitude is 4 and the lead 1 indicates that the magnitude is negative.

(43) By initializing the value of an accumulator, A.sub.0 to 2.sup.L+b, the value of the accumulator, A is offset by an amount equal to the value of b from the value at which b overflows. When generating long sequences (i.e., in which T is much greater than c), the value to which the accumulator A is initialized has less consequence. Accordingly, the accumulator can be initialized to any arbitrary value. However, for shorter strings in which T≤c, initializing the accumulator to 2.sup.L+b provides a more accurate result. The content A.sub.i of the accumulator A is then compared to 2.sup.L to determine whether A.sub.i is greater than 2.sup.L (STEP 1003). If b is positive, the comparison will be true. Alternatively, if b is negative, then the result of the comparison will be false. If true, then a bit n.sub.i of the δ-sequence, N is set to “1” and the value A.sub.i of the accumulator, A is decremented by 2.sup.L. (STEP 1005). If 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 value A.sub.i of the accumulator is updated to A.sub.i=A.sub.i−1+b+2.sup.L−1 (STEP 1011).

(44) FIG. 11 through FIG. 17 provide a graphic representation of the steps shown in the flowchart of FIG. 10. In FIG. 11, a circle 1100 is shown having zero/2.sup.L at the top (i.e., at zero degrees, top center) with values represented around the circle increasing linearly from 0 to 2.sup.L in a clockwise direction around the circle. 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 the position 2.sup.L=2.sup.4=16. A second pointer 1104 is shown pointing at the position A.sub.0=2.sup.L+b=16+4=20 (i.e., the point on the circle representing the value A.sub.0 to which the accumulator A is initialized when the index i=0). Upon performing the comparison in STEP 1003, the value of A.sub.0=20 is greater than 2.sup.L=16. Accordingly, on the first pass through STEP 1103, the answer is “true”. STEP 1005 is performed and the value of the first bit 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.

(45) FIG. 12 illustrates the value A.sub.i for i=0, which is calculated as A.sub.0=A.sub.0−2.sup.L=20−16=4 in STEP 1005. The arrow 1204 indicates the counterclockwise rotation of the pointer 1102 to the position shown for the pointer 1202. Note that the index is not yet incremented and the position of the pointer 1202 on the circle 1200 is the same for both values of A.sub.0; 20 and 4.

(46) FIG. 13 illustrates the condition once STEP 1009 has been performed. In STEP 1009 the index i is incremented. Next, STEP 1011 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. The pointer 1202 rotates to the top of the circle 1300, as shown by pointer 1302 and arrow 1304. The index i is then checked to see whether all of the bits of the δ-sequence, N have been generated (STEP 1013). If not, then the process returns to STEP 1003 in which the value A.sub.1 is compared to 16. Since A.sub.1=16 is equal to 2.sup.L=16 (i.e., STEP 1003 is true), STEP 1005 is performed. Accordingly, the value of n.sub.1 is set to 1 and the value of A.sub.1 is decremented to 0 (STEP 1005), as shown by the arrow 1306 indicating the counterclockwise rotation of the pointer 1302.

(47) FIG. 14 illustrates the incrementing of the index, i to 2 in STEP 1009, the calculation of the value of A.sub.2=A.sub.1+b+2.sup.L−1=0+4+8=12 in STEP 1011 and the resulting position of a pointer 1402 representing the value of A.sub.2. An arrow 1404 shows the rotation of the pointer 1302 to the new location 1402. Since A.sub.2=12 is less than 16, the value of the bit n.sub.2 as determined in STEP 1007 is set to 0.

(48) FIG. 15 illustrates the next pass through STEP 1009, in which the index is incremented to i=3. In STEP 1011, a new value is calculated for A.sub.3=A.sub.2+b+2.sup.L−1=12+4+8=24. An arrow 1504 shows the rotation of the pointer 1402 to the new location 1502. The index i is then checked to see whether all of the bits of the δ-sequence, N have been generated (STEP 1013). If not, then the process returns to STEP 1003. In STEP 1003, A.sub.3=24 is compared to 2.sup.L=16. Since A.sub.3 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 locates the new pointer at the same position, as indicated by arrow 1506.

(49) FIG. 16 illustrates the next pass through STEP 1009, in which the index is incremented to i=4. In STEP 1011, a new value is calculated for A.sub.4=A.sub.3+b+2.sup.L−1=8+4+8=20. An arrow 1604 shows the rotation of the pointer 1402 to the new location 1602. The index i is then checked to see whether all of the bits of the δ-sequence, N have been generated (STEP 1013). If not, then the process 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 locates the new pointer 1602 at the same position, as indicated by arrow 1606. It can be seen that the pointer 1602 is now back to the same location as the pointer 1202 shown in FIG. 12. Accordingly, when the index increments to i=5, the process will proceed exactly as it did when the index was incremented to i=1. Therefore, it can be seen that the value of the bit n.sub.5 will be set to 1 and the value of A.sub.5 will be calculated to be the same as the value of A.sub.1=16. Similarly, the value of the bit n.sub.6 will be set to 0, the same as bit n.sub.2 and the value of A.sub.6 will be calculated to be the same as the value of A.sub.2=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 1013). Once the index i, is equal to 2.sup.L−1=16−1=15, the process ends.

(50) FIG. 17 illustrates the result of the operation performed. In STEP 1013, the index i=15. Once the process determines that the index i has reached 15, each of the bits no through n.sub.15 will then have been determined and the process ends. 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 zero, there are three bits that are ones.

(51) FIG. 18 is an illustration of one embodiment for implementing the δ-sequence 1800. Initially, an index counter 1801 is initialized to a count of i=0. A clock coupled to the counter increments the counter to a terminal value of 2.sup.L−1, at which point the counter wraps around to zero (i.e., modulo 2.sup.L). The output of the index counter 1801 is coupled to the input of a comparator 1802. The comparator 1802 generates a select signal by comparing the index value i output from the index counter 1801 to zero. If i=zero, the select signal is one; otherwise, the select signal is zero. The select signal is coupled to a multiplexer 1803 that selects between an initialization value of 2.sup.L−1 coupled to an “x” input of the multiplexer and the current value stored in an accumulator A 1804 coupled to a “y” input to the multiplexer 1803 based on the select signal applied to the “s” input to the multiplexer 1803 from the comparator 1802. The select signal determines which of the inputs will be coupled to the output of the multiplexer 1803. The select signal causes the “x” input to be coupled to the output of the multiplexer 1803 when the index i is zero. The output of the multiplexer 1803 is coupled to a first input, A.sub.i−1 to a summing circuit 1806 when the index i is a value greater than zero.

(52) The multiplexer has two additional inputs, 2.sup.L−1 and b. The first of these additional inputs, 2.sup.L−1 is coupled a source of the value 2.sup.L−1 In accordance with some embodiments of the disclosed method and apparatus, the output of a register 1814 in which a value of 2.sup.L is stored is coupled to the input of a right shift register 1816. In such embodiments, the value 2.sup.L−1 is derived by performing a right shift of the output of the register 1814. Alternatively, a register (not shown) stores the value 2.sup.L−1 The second of the additional inputs, b is coupled to a memory register 1407 in which the value b is stored. The value b is the value to be converted from a two's complement binary representation to a BSBS sequence.

(53) The output of the summing circuit 1806 is the sum of the three outputs A.sub.i−1+b+2.sup.L−1 The output of the summing circuit 1806 is an intermediate value of A.sub.i. This intermediate value of A.sub.i coupled to three different circuits. The first of these three circuits is a comparator 1808. The second of the three circuits is a difference circuit 1810. The third of the circuits is a multiplexer 1812. The positive input to the comparator 1808 receives the output of the summing circuit 1806. The negative input to the comparator 1808 is coupled to the register 1814 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 1808 is a one. That is, if the sum A.sub.1=A.sub.i−1+b+2.sup.L−1 produced by the summing circuit 1806 is greater than 2.sup.L then the comparator outputs a “1”. Otherwise, the comparator outputs a “0”.

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

(55) Accordingly, when the value of the sum A.sub.i−1+b+2.sup.L−1 is greater than 2.sup.L, the multiplexer 1812 sets the value of A.sub.1 equal to A.sub.1 minus 2.sup.L. Alternatively, when the value of the sum A.sub.i−1+b+2.sup.L−1 is less than, or equal to 2.sup.L, the multiplexer 1812 sets the value of A.sub.i equal to the intermediate value of A.sub.i output from the summing circuit 1806.

(56) The output of the comparator 1808 is also coupled to the input to an N register 1818 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 1800 comprises very simple circuit element, such as a counter 1801, a summing circuit 1806, a difference circuit 1810, 2 comparators 1802, 1808, 2 multiplexers 1803, 1812, a shift register 1816 and four registers 1804, 1807, 1814, 1818.

(57) FIG. 19 is a flowchart of the steps performed by a δ-sequence generator to generate a USBS sequence. Initially, the accumulator value A.sub.0 is set to 2.sup.L−1+b (STEP 1901). If the initialized value of A.sub.0 is greater than or equal to 2.sup.L, then the bit no is set to 1 and the value of the accumulator is decremented by 2.sup.L (STEP 1905). Otherwise, if the value A.sub.0 is less than 2.sup.L, the value of the bit no is set to 0 (STEP 1907). In either case, the next step is to increment the index i (STEP 1909). For the unipolar SBS generator, the accumulator value A.sub.i is incremented by b (STEP 1911). The value of the index i is checked to see whether all of the bits have been generated by comparing the index value i, to 2.sup.L (STEP 1913). If equal, then the process ends. Otherwise, the process continues on, returning to STEP 1903.

(58) An SBS sequence generated using a δ-sequence has several properties of interest. The first of these properties is that, similar to the ω-sequence, the maximum error for the δ-sequence is less than 1/T. That is, converting a binary value to an SBS sequence, and then converting the SBS 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 an SBS sequence generated with an δ-sequence is that it can be generated without the use of a random number generator. Yet another property of an SBS that has been generated with an δ-sequence is that the SBS sequence will have the maximum number of transitions possible (state changes between one and zero). However, similar to an ω-sequence, an accurate product cannot be obtained when multiplying an SBS sequence that has been generated using a δ-sequence generator with another SBS sequence that has been generated using a δ-sequence. Neither can an accurate product be attained when multiplying a SBS sequence that has been generated using a δ-sequence with a time-shifted version of itself. Nonetheless, a SBS sequence that has been generated using an ω-sequence can be multiplied with a SBS sequence that has been generated using a δ-sequence.

(59) Another SBS generator that can be used in accordance with some embodiments of the disclosed method and apparatus generates an σ-sequence. Like the ω-sequence and δ-sequence, the σ-sequence is also a string that presents a numerical value in bipolar BSBS format. The σ-sequence may also be used either once or repeated multiple times within an SBS sequence. That is, several σ-sequence strings can be concatenated together to form one SBS sequence. The σ-sequence is similar to the ρ-sequence, but is more useful in cases in which it is desirable for the SBS sequences generated to obey the additive inverse identity property. That is, a ρ-sequence representing a binary value of b subtracted from another ρ-sequence representing the same value will result in zero if the two ρ-sequences are constructed using the same random number sequence.

(60) FIG. 20 is a flowchart of an algorithm that is used in some embodiments to generate a bipolar SBS σ-sequence. The process begins with a comparison of b to zero (STEP 2001). If b<0 is true, then a variable “SIGN” is set to 1 (STEP 2003). Otherwise, SIGN is set to 0 (STEP 2005). In either case, a second variable “mag” is set to the absolute value of b (STEP 2007). Next, an index counter is initialized to zero (STEP 2009). The index value, i of the index counter is incremented (STEP 2011). The value of i is checked to see whether the σ-sequence string is complete (i.e., whether the index, i=2.sup.L) (STEP 2013). If false, then mag is checked for mag <R.sub.i−2.sup.L−1 (STEP 2015), recalling that R.sub.i is a random number output from a PRNG. If true, the bit n.sub.i is set to the inverse of SIGN (STEP 2017). If false, then bit n.sub.i is set to SIGN (STEP 2019). The process returns to STEP 2011 and end when STEP 2015 is true.

(61) FIG. 21 is an illustration of an example of a circuit for implementing a σ-sequence generator 2100. A reset signal is initially applied to an index counter 2102 to reset the index, i output of the counter 2102 to zero. The index i is coupled to the input of a pseudo random number generator (PRNG) 2104. For each distinct value of i, the PRNG 2104 outputs a random value, R.sub.i. within the range of zero to 2.sup.L−1. The output R.sub.i of the PRNG 2104 is coupled to a first input of a difference circuit 2106. A second input of the difference circuit 2106 is coupled to the output of a register 2108 in which the value 2.sup.L−1 is stored. The difference circuit 2106 outputs the difference R.sub.i−2.sup.L−1 which is coupled to the negative input (i.e., inverting input) of a comparator 2110. The positive input is coupled to the output of an absolute value circuit 2112. The input to the absolute value circuit 2112 is coupled to the output of a register 2114 in which the value of b is stored.

(62) The comparator 2110 compares the absolute value of b to each random number, R.sub.i generated by the PRNG 2106 as the index counter 2102 increments through the index values, i. For each value of i, the comparator determines whether the absolute value of b is greater than the difference R.sub.i−2.sup.L−1 With the random values, R.sub.i output from the RNG 2106 being in the range from 0 through 2.sup.L−1, and assumed to be truly random, the probability that the output of the comparator 2110 will be true is equal to p=(b+2.sup.−1)/2.sup.L for values of b that are in the range of −2.sup.L−1 to 2.sup.L−1. It can be seen that the term (b+2.sup.L−1) shifts the value of the numerator upward from the value of b by 2.sup.L. This serves to effectively place the range of numerator in a range from 0 to 2.sup.L−1.

(63) The output of the comparator 2110 is coupled to a select input of a multiplexer 2115. Accordingly, the output of the comparator 2110 determines whether the “x input” or the “y input” of the multiplexer 2115 is coupled to the multiplexer 2115 output. The “x input” is coupled directly to the output of a SIGN register 2116. The SIGN register 2116 stores a value that is provided by the output of a comparator 2118. The comparator 2118 is a “1” for values of b that are less than zero (negative) and “0” for values of b that are greater than or equal to zero. The “y input” to the multiplexer 2115 is coupled to an inverter 2120. The input of the inverter 2120 is coupled to the output of the SIGN register 2116. The output of the multiplexer 2115 is coupled to a register 2122 that stores each of the values of the bits, n.sub.i of the string N under the control of the index, i.

(64) Accordingly, the probability that n.sub.i is set to the value stored in the SIGN register 2116 is equal to p=(b+2.sup.L−1)/2.sup.L the probability that the output of the comparator 2110 is a “1”. The benefit gained by generating an SBS sequence using the α-sequence generator is that such a SBS sequence will obey the additive inverse identity, assuming the same string of values R.sub.i is used to generate both the SBS sequences that represent the positive value and the negative value that are summed. In the case in which the PRNG 2104 is a pseudo random number generator, the values of R.sub.i will be the same if the same seed is used to generate the values of R.sub.i. All of the other characteristics of SBS sequences generated using the σ-sequence generator are the same as those of SBS sequences generated using a ρ-sequence generator.

(65) Another SBS generator that can be used in accordance with some embodiments of the disclosed method and apparatus generates a ζ-sequence. Like the ω-sequence, δ-sequence, and σ-sequence, the ζ-sequence is also a string that presents a numerical value in bipolar BSBS format. The ζ-sequence may be used either once or repeated multiple times within an SBS sequence. That is, several ζ-sequence strings can be concatenated together to form one BSBS sequence. ζ-sequence strings always represent a value of zero, and are of particular use when multiplying by zero.

(66) A ζ-sequence has two parameters that define the nature of strings generated using a ζ-sequence generator. These parameters are referred to herein as “r” and “s”, where r is an integer of value 1 or greater and s is an integer in the range of 0 to r−1. A ζ-sequence string is defined as having s bits that are assigned a value of “0”, followed by r bits assigned a value of “1”, followed by r−s bits assigned a value of “0”. Accordingly, the total number of bits, T in string generated with a ζ-sequence generator is T=r+s+r−s=2r.

(67) The following are examples of some strings that contain multiple instances of a ζ-sequence, ζ(r,s): ζ(1,0): [10].sup.T=2r=2=10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 1 . . . ζ(2,0): [1100].sup.T=2r=4=1100, 1100, 1100, 1100, 1100, 1100, 1100, 1 . . . ζ(2,1): [0110].sup.T=2r=4=0110, 0110, 0110, 0110, 0110, 0110, 0110, 0 . . . ζ(3,2): [001110].sup.T=2r=6=001110, 001110, 001110, 001110, 001110, 0 . . .

(68) Commas are inserted between each individual ζ-sequence within the string generated by concatenating several ζ-sequences together. The value within the brackets indicates the pattern of ones and zeros within the ζ-sequence. The superscript indicates the length of the ζ-sequence. It can be seen that there will be r bits assigned to a value of “1” and the same number, s+r−s=r bits assigned to a value of “0”. Thus, the resulting ζ-sequence always represents a value of zero. However, the pattern of “1”s and “0”s can be defined by setting the values of the parameters, r and s.

(69) FIG. 22 is a flowchart of the method used to generate a ζ-sequence. The process begins by outputting s zeros (STEP 2201). Using the first example, ζ(r,s)=ζ(1,0), since s=0, there are no leading zeros in the string (i.e., no output is provided in STEP 2201). Next, since r=1, the number of bits that are output with an assigned value of “1” is 1 (STEP 2203). Finally, since r−s=1, an additional bit is output with a value assigned to “0” (STEP 2205). This process can be repeated to form a BSBS sequence that has a length that is an integer multiple of 2r.

(70) FIG. 23 is a simplified illustration of one embodiment for implementing a ζ-sequence generator 2300. Three partial string registers 2302, 2304, 2306 each have an index input coupled to an output of a corresponding decrementing index counter 2308, 2310, 2312. The first decrementing index counter 2308 has a preset input coupled to a register 2314 loaded with a value of s−1, the second 2310 has a preset input coupled to a register 2318 loaded with a value of to a value of r−1, the third 2312 has a preset input coupled to a register 2318 loaded with a value of r−s−1. A clock signal is coupled to each of the decrement counters 2308, 2310, 2312 to start the counters decrementing from their respective pre-load values. Each counter is initialized to the pre-load value. The pre-load values are re-loaded each time the count value is zero, creating modulo s, r and r−s counters, respectively. The outputs partial string register 2302, 2304, 2306 is coupled to string register 2326. The string register 2326 loads the bits no through n.sub.2r−1 from each of the partial string registers 2302, 2304, 2306 and outputs the string N, which comprises the bits no through n.sub.2r−1.

(71) A string generated with a ζ-sequence generator will always represent a value of zero, assuming the length of the BSBS sequence is either 2r or an integer multiple of 2r. It should be noted that a BSBS sequence generated using a ζ-sequence (1, 0) generator will be identical to a BSBS sequence of the same length generated with a δ-sequence generator and representing a value of zero. This is not true for other sets of parameters. In addition, the product of a first string ζ(r.sub.1,s.sub.1) and a second string ζ(r.sub.2,s.sub.2) will always be equal to 0, if r.sub.1 is not equal to r.sub.2 or s.sub.1 is not equal to s.sub.2 and the length of the product of the two strings is equal to 2×r.sub.1×r.sub.2, or an integer multiple thereof. Furthermore, a BSBS sequence generated using a ζ-sequence generator multiplied by a either a BSBS sequence generated using a δ-sequence generator or a ω-sequence generator will result in a product that has a value, P that is less than or equal to r of the BSBS sequence generated with a δ-sequence generator, assuming the length, T of the string is equal to, or an integer multiple of 2r. Also, the product, P of a BSBS sequence generated using a ζ-sequence generator and a BSBS sequence generated using a σ-sequence generator will have a value with a mean of 0 and a scaled standard deviation proportional to the square root of (p(1−p))/T. Lastly, a BSBS sequence generated using a ζ-sequence generator can be multiplied by a time shifted version of itself, as long as the amount of the shift is not equal to r or an integer multiple of r.

(72) FIG. 24 is an alternative embodiment for implementing a ζ-sequence generator 2400 for generating sequences of ζ(r,s)=ζ(1,0). The output of a register 2402 is coupled to the input of an inverter 2404. The output of the inverter 2404 is fed back around to the input of the register 2402. The output bits are taken from the register 2402. Initially, the register 2402 is reset to zero by a reset signal. A clock 2406 generates a clock signal applied to the register 2402 to move the signal at the input of the register to the output of the register 2402. In some embodiments, a counter 2408 is used to count the clock pulses and establish an index i that indicates the particular bit being generated (i.e., n.sub.i of the, ζ(r,s) sequence, N). As the clock signal moves the bit through the register 2402 and inverter 2404, the output will alternate between 1 and 0, generating the desired output stream. It should be noted that the “0” noted in the register of FIG. 24 does not indicate the value stored in the register, but rather the position of the register within the generator 2400, as will become clearer as the implementations shown in FIG. 25, FIG. 26, FIG. 27 and FIG. 28 are disclosed below.

(73) FIG. 25 is a simplified schematic of ζ(r,s)=ζ(2,0) generator 2500. The generator 2500 comprises a circular shift register with a “zeroth” register element 2402, a first register element 2502, an inverter 2404, a clock 2406 and a counter 2408. The zero in the register element 2402 indicates that it is the zeroth element. The one in the first register element 2502 indicates that it is the first register element. Each of the register elements 2402, 2502, 2702 is reset by the reset signal and shifted by the clock signal. The generator 2500 works similar to the generator 2400, but the addition of the second register element 2502 causes the output to alternate between pairs of ones and pairs of zeros, with the first two bits, no, n.sub.i, being zero followed by the next two bits, n.sub.2, n.sub.3 being ones, this pattern then repeating. It should be noted that while the register elements 2402, 2502 are shown to have values of 1 and 0, respectively, they are both initially reset to zero.

(74) FIG. 26 is a simplified schematic of ζ(r,s)=ζ(2,1) generator 2600. The generator 2600 comprises a circular shift a “zeroth” register element 2402, a first register element 2502, an inverter 2404, a clock 2406 and a counter 2408 just like the generator 2500 of FIG. 25. Each of the register elements 2402, 2502, 2702 is reset by the reset signal and shifted by the clock signal. The generator 2600 works the same as the generator 2500, but the output is taken from the first register element 2502, causing only the first bit that is output to be zero, there after the output alternates between pairs of ones and pairs of zeros. Accordingly, with the first bit, n.sub.0 is zero, the second bit n.sub.1 is one, the third bit, n.sub.2, is one and the fourth bit, n.sub.3 is zero. This pattern then repeats.

(75) FIG. 27 is a simplified schematic of ζ(r,s)=ζ(3,2) generator 2700. The generator 2700 comprises a circular shift register with three register elements 2402, 2502, 2702, an inverter 2404, a clock 2406 and a counter 2408. Each of the register elements 2402, 2502, 2702 is reset by the reset signal and shifted by the clock signal. The generator 2700 works similar to the other ζ(r,s) generators 2400, 2500, 2600. The output is taken from the first register element 2702, causing the first bit, no to be a zero, but each of the following three bits, n.sub.1, n.sub.2, n.sub.3 will be ones. The desired pattern of one zero, followed by three ones, followed by 2 zeros will repeat (i.e., 011100,011100 . . . ).

(76) FIG. 28 is a simplified schematic of ζ(r,s)=ζ(3,1) generator 2800. The generator 2800 comprises a circular shift register with three register elements 2402, 2502, 2702, an inverter 2404, a clock 2406 and a counter 2408. Each of the register elements 2402, 2502, 2702 is reset by the reset signal and shifted by the clock signal. The generator 2800 works the same as the ζ(r,s) generator 2700, but the output is taken from the second register element 2502, causing the first two bits, n.sub.0, n.sub.1 to be a zero, followed by three bits, n.sub.2, n.sub.3, n.sub.4 will be ones and a 6.sup.th bit n.sub.5 that is a zero. The desired pattern of two zeros, followed by three ones, followed by 1 zero will repeat (i.e., 001110,001110 . . . ).

(77) It can be seen that the implementation of ζ(r,s) generator can be generalized by noting that r register elements are provided, with the output being taken by the register element indicated by s. In the case of the generator 2800, there are r=3 register elements 2402, 2502, 2702, with the output being taken from the first register element 2502, as indicated by s=1. In a ζ(3,0) generator, the output would be taken from the zeroth register element 2402.

(78) Yet another SBS generator that can be used in accordance with some embodiments of the disclosed method and apparatus generates a “prime”-sequence, i.e., σ′.sub.r,s-sequence and ρ′.sub.r,s-sequence. These prime-sequence generators are modifications of their underlying sequences. That is, the σ′.sub.r,s sequence is a modification of the σ-sequence. The modification is that for b=0, the BSBS sequence is generated using a ζ-sequence generator, but for all other values of b, a σ-sequence generator is used to generate the BSBS sequence. Similarly, the ρ′.sub.r,s-sequence is generated using a ρ-sequence generator for all values of b except b=0, for which a ζ-sequence generator is used. Generating BSBS sequences using a ρ′.sub.r,s-sequence generator or a σ′.sub.r,s-sequence generator improves the behavior of the standard ρ-sequence and σ-sequence generators for b=zero by ensuring that the error for multiplication by zero is minimized.

(79) γ-sequences

(80) γ-sequences are a slight modification to the ρ-sequence and σ-sequence, in which a comparison values (i.e., those values that are compared to b to determine the bit value) are created by a generator function G.sub.L(i) that maps values of the index, i into the space that includes integer values in the range from −2.sup.L−to 2.sup.L−1−1. The generator function may be a hash function that is “random”, such as an L-bit cyclic redundancy code (CRC) in which a fixed bit sequence serves as the seed and the input is the index value, i.

(81) The γ-sequence generator operates the same way as the ρ-sequence generator described above, but for the use of the function G.sub.L(i) in place of the RNG output. A prime sequence generator for the γ′.sub.r,s-sequence operates the same way as the γ-sequence generator described above, but for the use of the function GL(i) in place of the RNG output. The advantage provided by the γ-sequence generator is the fact that it does not require a linear-feedback shift register (LFSR), as is required for the PRNG that is used to generate the RNG output in the ρ-sequence generator and the σ-generator described above.

(82) Each of the above described sequence generators can be provided as sub-blocks in a single BSBS sequence generator and selected based upon the particular characteristics of the operation to be performed on the resulting BSBS sequence and the conditions under which the string is being generated. By providing flexibility in determining which particular generator is best suited to a particular situation, the advantages of each generator can be maximized for each particular situation.

(83) FIG. 29 is a simplified block diagram of a generator comprising a plurality of SBS generator sub-blocks 2902, 2904, 2906, 2908, 2910 each sub-block generating an SBS sequence using a different technique. A processor 2912 is coupled to a multiplexer 2914 and controls the selection by multiplexer 29014 of the generator sub-block 2902, 2904, 2906, 2908, 2910 to be coupled to the input of a register 2916, 2918 in which the value of BSBS sequences generated by the generator sub-blocks 2902, 2904, 2906, 2908, 2910 are stored. In alternative embodiments, the output of each of the sub-blocks 2902, 2904, 2906, 2908, 2910 may be stored in a different register. Those registers 2916, 2918 can then be selectively coupled to a set of logic gates 2920, such as exclusive NOR (XNOR) gates that perform the multiplication of the strings output by the sub-blocks 2902, 2904, 2906, 2908, 2910.

CONCLUSION

(84) 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.