Apparatus for Generating Digital Streams Having Variable Probabilities of Error

This invention relates generally to the field of electrical error signal generators and more particularly to the field of electrical signal generators which are capable of generating binary digital streams having predetermined probabilities of error.

Frequently, during the design and testing phases of digital hardware, designers require equipment which will enable them to test the operation and performance of their prototype designs under various error conditions, in order to compare actual and predicted performance. In addition, error testing is a maintenance tool which is commonly used by maintenance personnel to monitor the performance of digital equipment or systems. This is particularly true in the communications industry, where data transmission equipment must operate reliably in the presence of noise. Noise added to digital signals during transmission or produced in equipment, can result in errors in the received data. Consequently, it is common for data transmission systems to employ complicated coding schemes, and error detection and correction circuitry in order to detect and correct errors in the data. Error testing is essential to insure that these circuits are performing properly.

One commonly used error testing technique involves generating known digital data, such as a predetermined code sequence of 1's and 0's, in which one or more bits of the sequence are altered in accordance with some predetermined scheme. The corrupted sequence is then input to the device under test, and the output of the device is compared with the originally generated data, to determine whether or not the errors were detected. Since the performance of equipment is most commonly measured in terms of its probability of detecting errors, it is convenient to be able to generate test sequences having known probabilities of error.

Although test equipment is generally available for this purpose, most commercially available equipment is either costly, difficult to use in terms of being able to set up specific probabilities of error, or limited in the range of error probabilities which it is capable of generating.

It is desirable to have an apparatus which will overcome the aforesaid disadvantages and it is to this end that the present invention is directed. Accordingly, there is provided by the invention, a new and improved apparatus, useful in performing error testing of digital equipment and systems, which is capable of generating digital test signals having specifiable probabilities of error over a large range of probabilities and which is easily implementable in hardware.

The invention is based upon the recognition of the fact that there exists a class of boolean functions having the general form

where x.sub.i, i = 1, 2, . . . n, are random variables and a.sub.i are coefficients having a value of 0 or 1, having three interesting properties. These properties are:

I. There is a 1-to-1 correspondence between the set of all possible biases of the form k/2.sup.n, where k is odd, and the functions of this class.

II. The function is easily derivable from the bias value.

III. The function is easily implementable in hardware.

As used herein, bias is defined as the probability of the function having the value binary 1, over all possible input patterns of the random variables x.sub.i. In particular, for n random variables, these functions have biases, i.e., probabilities of having the value 1, of the form k/2.sup.n, where k is odd. Furthermore, since each function of the class is defined by the values of the coefficients a.sub.i, the first property above, I., implies that each function of the class has associated with it a unique value of bias and conversely that each value of bias is associated with a unique set of coefficients a.sub.i. Furthermore, implicit in the above is the fact that if the random variables represent random binary streams, which are combined in hardware in accordance with a function of the class defined by equation (1), the output digital stream will have a bias determined by the values of the coefficients a.sub.i. Consequently, this output stream having a known probability of occurrence of 1's, can be combined with a known sequence of 1's and 0's to provide a test sequence having a known probability of error. This test sequence is useful in the testing of digital equipment.

Accordingly, it is an object of the invention to provide an apparatus for generating digital streams having specified probabilities of error.

It is also an object of the invention to provide such an apparatus in which the specified probability of error is easily selectable.

An apparatus having these and other advantages may include means for generating n independent, random digital streams, means for combining the random streams into a single output digital stream in accordance with a combining function of the form

where x.sub.1, x.sub.2 . . . x.sub.n are variables representing the random digital streams and a.sub.1, a.sub.2 . . . a.sub.n-1 are coefficients of the variables having the value 0 or 1, and means connected to the combining means for selecting the values of the coefficients such that the output digital stream has a probability of the occurrence of a 1 of the form k/2.sup.n, where k is an odd number less than 2.sup.n.

Other objects and advantages of the invention will be apparent from the following detailed description and upon reference to the drawings, in which:

FIG. 1 is a functional block diagram of an implementation of the generalized combining function of equation (1);

FIG. 2 (a) illustrates a digital logic implementation of equation (1) for an apparatus capable of generating probabilities between 1/16 and 15/16;

FIGS. 2(b) and 2(c) define respectively the logical AND and the MOD 2 functions;

FIG. 2 (d) is a table giving the values of the coefficients of the apparatus of FIG. 2(a) corresponding to various probabilities; and

FIG. 3 illustrates an embodiment of an error generator constructed in accordance with the invention.

FIG. 1 illustrates functionally the manner in which the class of functions defined by equation (1) may be implemented. The random variables, x.sub.i, are represented by a plurality of blocks 10-13 which are combined in an interconnected series of multipliers 16-18 and adders 20-23. Except for variable x.sub.1, 10, each of the random variables is input to one of two inputs of multipliers 16-18. The second input to the multipliers is the output of an adder 20-23 which adds the value of one of the coefficients, a.sub.i, represented by blocks 25-28, to the output from the preceeding mulitplier. Variable x.sub.1, 10, is first added to coefficient a.sub.0 in the first adder 20 prior to being input into the first multiplier 16.

It is easily demonstrated, that the apparatus defined by the block diagram of FIG. 1, implements equation 1. For example, the output of the first adder 20 of FIG. 1 is obviously (x.sub.1 + a.sub.0), which corresponds to the intermost parenthetical term in equation (1). This term is then multiplied by the variable x.sub.2, 11, in the first multiplier 16 and the result is added to a.sub.1, 26, in the second adder 21. This produces (x.sub.2 (x.sub.1 + a.sub.0) + a.sub.1) corresponding to the second intermost parenthetical term in equation (1), and so forth.

For n independent random variables, the output bias or probability of the device illustrated functionally in FIG. 1, is equal to k/2.sup.n where k is an odd number less than 2.sup.n. Furthermoe, it can be shown that the output bias is independent of the value of coefficient a.sub.0. Hence, a.sub.0 may be arbitrarily taken to equal 0 and equation (1) rewritten as

Taking a.sub.0 to equal 0, permits the first adder 20 of FIG. 1 to be eliminated and the x.sub.1 variable 10 to be input directly to the first multiplier 16.

In digital logic, the adder function of FIG. 1 may be implemented as a MOD 2 adder and the multiplier function of FIG. 1 may be implemented as an AND gate.

FIG. 2(a) illustrates a digital logic implementation of the apparatus of FIG. 1. A combiner 30 combines four random digital streams (n = 4) in accordance with equation (2), such that an output digital stream is obtained having any desired bias of the form k/2.sup.4 between 1/16 and 15/16, for k odd.

Four random generators 33-36 are used to generate four random digital streams. The random digital streams are combined in combiner 30 comprising AND gates 40-42 and MOD 2 adders 45-47. For the apparatus of FIG. 2(a), n = 4, and equation (2) reduces to

The AND logic function is defined in FIG. 2(b). As illustrated, the output, c, of the AND gate is 0 if either both inputs a and b are 0 or both inputs are different. The output is 1 only if both inputs a and b are 1's.

FIG. 2(c) illustrates the MOD 2 (exclusive-OR) logic function. If both inputs a and b to the MOD 2 adder are the same, i.e. both 0's or 1's, the output is 0. However, if the two inputs differ the output is 1. Another way of viewing the MOD 2 function is that if one of the inputs is held at a binary 1 the other input is inverted at the MOD 2 adder output. For example, if input b of the MOD 2 adder in FIG. 2(c) is = 1, the output will be 1 if input a = 0 and 0 if input a = 1. Therefore, the MOD 2 adders can be viewed as a controlled inverter, which will selectively invert one input depending upon whether or not the control input is a 1 or a 0.

In FIG. 2(a), each of blocks 50-52 provide an output which represents the value, either a 0 or a 1, of one the coefficients, a.sub.i. In the apparatus of FIG. 2(a), blocks 50-52 representing the coefficients can be any means for providing either a 0 or a 1 to the MOD 2 adders 45-47. The simplest such means would be switches having terminals connected to logic 1 and logic 0 levels, which simply select the value of binary 1 or binary 0 depending the desired value for the coefficient.

Random generators 33-36 in the apparatus of FIG. 2(a) represent the random variables x.sub.i of equations (1) and (2) as previously described. The random generators 33-36 produce an output binary stream which is random, i.e. the probability of the random generator outputting a binary 1 is equal to the probability that the random generator will output a binary 0. Therefore, each random generator has the probability of outputting a binary 1, designated by p, equal to 1/2.

In FIG. 2(a), the outputs of random generators 33 and 34, each having p = 1/2, are multiplied in AND gate 40. Therefore, the probability of a 1 appearing on the output of AND gate 40 is p = 1/2 .times. 1/2 = 1/4. If, for example, coefficient a.sub.1 is assumed to have the value 1, the probability of a 1 appearing on the output of MOD 2 adder 45 will be 3/4, i.e. if a.sub.1 is equal to 1, as previously mentioned, the other input to MOD 2 adder 45 will be inverted on the output. If the probability of the occurrence of a 1 on the input to adder 45 from gate 40 is equal to 1/4 and this input is inverted in MOD 2 adder 45 due to a a.sub.1 being 1, the output of MOD 2 adder 45 obviously has the probability of occurrence of a 1 equal to 3/4. AND gate 41 then multiplies this output from MOD 2 adder 45 by the output from random generator 35 resulting in the input to MOD 2 adder 46 having a probability equal to 3/4 .times. 1/2 or 3/8. If then, coefficient a.sub.2 is assumed to be equal to 0, the output of MOD 2 adder 46 to AND gate 42 will also be 3/8. Since random generator 36 also has p = 1/2, the output of AND gate 42 will be 3/16. The output of AND gate 42 is then input to MOD 2 adder 47 to be added with the value of coefficient a.sub.3. If a.sub.3 is equal to 0, the output of MOD 2 adder 47, which is the output of combiner 30, will be 3/16. Therefore, with coefficients a.sub.1, a.sub.2, a.sub.3, = 1, 0, 0, the apparatus of FIG. 2(a) will generate an output binary stream having a probability of occurrence of 1's equal to 3/16. This corresponds to the second line of the table in FIG. 2(d).

The table of FIG. 2(d) gives the values for the coefficients a.sub.1, a.sub.2, a.sub.3 to generate any odd probability between 1/16 and 15/16. It can be seen from FIG. 2(d), that associated with each probability p, there is a unique set of coefficients a.sub.1, a.sub.2, a.sub.3.

For any n and bias k/2.sup.n, a vector I can be defined, where I = (a.sub.1, a.sub.2, . . . a.sub.n-1) is the inversion pattern of coefficients necessary to produce a desired bias. Furthermore, this inversion pattern is unique for each value of k, where k is odd and less than 2.sup.n.

There exists a simple algorithm for determining the set of coefficients corresponding uniquely to each value of bias. For example, for the apparatus illustrated in FIG. 2(a), suppose it is desired to determine the coefficients corresponding to a bias of 13/16. In this case, k = 13 and n = 4, i.e., 2.sup.4 = 16. The value of k is first written in binary form as a sum of a series of powers of 2, to degree n-1. In binary form, k may be expressed as

where b.sub.0, b.sub.1, . . . b.sub.n-1 are coefficients having a value 0 or 1. For k = 13 equation (4) becomes

Neglecting the value of coefficient b.sub.0, the 3-tuple consisting of the three higher order coefficients of the powers of two (b.sub.1, b.sub.2, b.sub.3) is

The rightmost bit of (6), corresponding to b.sub.3, is taken to be the value of coefficient a.sub.3, i.e. 1, and this bit is MOD 2 added to each of the remaining bits of (6) to produce the 2-tuple

Coefficient a.sub.2 is set equal to the rightmost bit of (7), i.e. 0, and this bit is MOD 2 added to the remaining bit of (7) to produce the 1-tuple

This bit is taken to be the value of coefficient a.sub.1 and the vector I = (a.sub.1, a.sub.2, a.sub.3) becomes

which corresponds to the coefficient values indicated in the table of FIG. 2(d) for p = 13/16. The remaining sets of coefficients corresponding to the other biases given in FIG. 2(d) can be found in a similar manner.

This algorithm may generalized in that the value of any coefficient, a.sub.n-i, for (1.ltoreq.i.ltoreq.n-1), may be found from the MOD 2 addition of the b.sub.n-i and the b.sub.n-i+l coefficients of the binary representation of k. In equation form

for (1.ltoreq.i.ltoreq.n-1), where the symbol .sym. represents MOD 2 addition. To illustrate, in the above example, b.sub.1, b.sub.2, b.sub.3 = 0, 1, 1. Therefore, n = 4 and from equation (10), the value of a.sub.3 = b.sub.3 .sym. b.sub.4, (i = 1). The coefficient b.sub.4 is obviously 0 and b.sub.3 = 1. Thus, a.sub.3 = 1 .sym. 0 = 1, as before. Similarly, a.sub.2 = b.sub.2 .sym. b.sub.3 = 1 .sym. 1 = 0 and a.sub.1 = b.sub.1 .sym. b.sub.2 = 0 .sym. 1 = 1.

The apparatus in FIG. 2(a) can be extended to generate any bias k/2.sup.n, for k odd and less than 2.sup.n by the addition of AND gates and MOD 2 adders to combiner 30. The vectors I = (a.sub.1, a.sub.2, . . . a.sub.n-1) representing the sets of n-1 coefficients corresponding to each odd bias between 1/2.sup.n and 2.sup.n 1/2.sup.n can be determined using the above described algorithm.

It is necessary that random generators 33-36 in FIG. 2(a) generate independent, flat, random digital streams for input to combiner 30. This means that the random generators 33-36 should be unbiased, i.e., have equal probabilities of occurrence of 1's and 0's and that the random streams be independent of each other, or at least sufficiently uncorrelated so as to insure that there is no interdependence among them. Random generators 33-36 may be implemented in a number of ways known to those skilled in the art. For example, each may be implemented by using a noise diode as a source of random noise which is input to a voltage comparator. The comparator outputs a 1 when its input voltage exceeds a set threshold. This threshold can be adjusted such that there is an equal probability of the comparator outputting a 1 or a 0. The comparator outputs can then be clocked by some reference frequency, utilizing logic gates, to output the random streams at any desired rate.

The apparatus of FIG. 2(a) may also be designed to operate over a limited range of biases or at a number of fixed, specified biases, thereby permitting simplification of combiner 30. For example, inspection of FIG. 2(d) reveals that coefficient a.sub.3 is equal to 0 for all biases between 1/16 and 7/16. If an apparatus with biases only within this range is required, it is possible to eliminate MOD 2 adder 47 and coefficient generator 52 corresponding to coefficient a.sub.3, since a 0 input to MOD 2 adder 47 from 52 simply allows the output of AND gate 42 to pass through the MOD 2 adder uninverted. Furthermore, the MOD 2 adders 45-47 could be replaced with inverter amplifiers and switches which select either the inverted output from the amplifier or the non-inverted output from AND gates 40-42. A coefficient value of 1 would correspond to the inverted output from the amplifier while a value of 0 would correspond to the non-inverted output from the AND gate.

A slight modification of the apparatus of FIG. 2(a) also permits the apparatus to generate biases for k even. For example, if k = 2m, then p = 2m/2.sup.n = m/2.sup.n-1. If random generator 36 is caused to have p = 1, i.e. a constant 1 input to AND gate 42, then the apparatus of FIG. 2(a) will generate biases of the form m/2.sup.n-1 for m odd. This permits biases between 1/8 and 7/8 to be generated, which is equivalent to biases between 2/16 and 14/16.

FIG. 3 is an illustration of an error generator embodying the principles of the invention, which is capable of generating various probabilities between 1/2.sup.16 and 4095/2.sup.16. The apparatus of FIG. 3 utilizes two feedback shift registers, X-register 55 and Y-register 56 to generate independent random digital streams for input to combiner 57. Shift registers 55 and 56 utilize MOD 2 adders 60--60 between selected stages in order to provide feedback. The position of MOD 2 adders 60--60 between stages is selected so that each register 55 and 56 will generate a maximal length pseudo-random sequence. The X-register 55 is a 35 stage shift register which has a cycle length of 2.sup.35 - 1 for the illustrated feedback connections. The Y shift register 56 is a 33 stage shift register having a cycle length of 2.sup.33 - 1. Taps 61--61, 62--62 are provided from selected stages of both shift registers 55 and 56 respectively. As illustrated, the X-register 55 is provided with eight taps 61--61 from stages 3, 8, 10, 17, 19, 24, 28 and 33. Similarly, the Y-register 56 is provided with eight taps 62--62 from stages 3, 8, 11, 16, 18, 24, 27 and 32. This gives a total of sixteen random streams for input to combiner 57.

Combiner 57 comprises a plurality of AND gates A1-A13, inverter amplifiers 66--66 and switches 67--67. Each of the eleven switches 67--67 corresponds to one of coefficients a.sub.1, a.sub.2 . . . a.sub.11. Inverter amplifiers 66--66 and switches 67--67 are connected as illustrated, on the output of the first 11 AND gates, A1-A11, such that either an inverted or a non-inverted output may be selected for input to the next succeeding AND gate. Inverter amplifiers 66--66 and switches 67--67 perform the same functions as the MOD 2 adders and coefficient generators of FIG. 2(a).

The first AND gate, A1, has one input terminal 70 connected to the tap 61 of X-register stage 3, as indicated by the designation X3, and the other input terminal 71 is connected to tap 62 of stage 3 of Y-register 56, as indicated by the designation Y3. AND gates A2-A11 have one of their inputs derived from one of switches 67--67, which selects either the inverted or the non-inverted output of a preceeding inverter amplifier or AND gate. The other input is connected to one of the taps 61--61 or 62--62 of either register 55 or register 56. These inputs are indicated by either the letter X or the letter Y and a numeral to indicate the register and stage from which the input is derived. AND gate A12 is a four input AND gate having its four inputs connected to four taps of registers 55 and 56. AND gate A13 has one input connected to the output of AND gate A12 and the other input connected to the switch output, of AND gate A11. The output on terminal 75 is a binary stream having a bias determined by the positions of switches 67--67. The binary stream output on terminal 75 is at the same rate as registers 55 and 56 are stepped.

The taps 61--61, 62--62 of the stages of shift registers 55 and 56, as well as their connection to AND gates 65--65 of combiner 57, were selected so that the input streams to the AND gates of combiner 57 were reasonably uncorrelated, in order to simulate independent, random generator inputs.

TABLE 1, below, gives switch settings for switches 67--67 corresponding to coefficients a.sub.1, a.sub.2 . . . a.sub.11, for various probabilities between 0.0001 and 0.05 for the apparatus of FIG. 3. A "0" indicates that the switch position is such as to select the non-inverted output from the corresponding AND gate. A "1" indicates selection of the inverted output from the corresponding inverter amplifier. For each probability listed in Table 1 the switch settings are the previously described inversion pattern or I vector, which corresponds to the values of the coefficients of equation (2). Extensive computer simulations were conducted on the apparatus illustrated in FIG. 3 to determine how well its actual performance matched its theoretical performance. The column labeled "Actual" in the table gives the actual measured probabilities corresponding to the predicted probabilities listed therein.

To utilize the apparatus of FIG. 3 for error testing, it is sufficient to provide the binary stream on output terminal 75 to a MOD 2 adder, the other input of which is a known code sequence, stepped in synchronism with registers 55 and 56. Each time a 1 appears in the binary stream generated by the apparatus of FIG. 3 the MOD 2 adder will cause an inversion to occur in the corresponding bit of the code sequence. This will produce a binary stream out of the MOD 2 adder having a known probability of error, which can be fed to a device under test.

While the foregoing description has been reference to particular embodiments, it will be appreciated by those skilled in the art that variations are possible without the departing from the spirit and intent of the invention. It is intended that the invention be limited only by the appended claims.