2ⁿ-1 Shuffling network

[0001] This invention relates to 2ⁿ−1 shuffling network.

[0002] In a binary segmented system, such as a digital to analog converter (DAC), for example, a unary array of 2ⁿ−1 elements may be used to represent n bits of an (m+n) bit array. The 2ⁿ−1 unary element array may be used with other circuit elements of lower bit significance to form the total (m+n) bit array; in such a case the lower significant circuit elements would sum to an approximate equivalent significance as a single element of the 2ⁿ−1 element unary array. In such systems, shuffling schemes can be used to reduce the effects of mismatch between circuit elements. Where mismatch between a unary array of 2ⁿ−1 elements is required a scheme for generating only 2ⁿ−1 unique shuffled outputs is required; a shuffling scheme generating 2ⁿ unique outputs when mapped to a 2ⁿ−1 unary array would have a repetitive sequence causing less than ideal shuffling auto-correlation.

[0003] It is therefore an object of this invention to provide an improved 2ⁿ−1 shuffling network.

[0004] It is a further object of this invention to provide such an improved 2ⁿ−1 shuffling network particularly useful for reducing the effect of mismatch errors in digital to analog converters.

[0005] It is a further object of this invention to provide such an improved 2ⁿ−1 shuffling network which reduces the autocorrelation of shuffling sequence which in turn reduces colored or harmonic noise.

[0006] This invention results from the realization that an improved 2ⁿ−1 shuffling network which reduces the effect of mismatch errors and reduces autocorrelation and concomitant colored or harmonic noise can be achieved using a replacement set of 2ⁿ−1 data switches for receiving 2ⁿ−1 outputs from a shuffle exchange network which receives 2ⁿ−1 inputs and a dummy input and provides 2ⁿ outputs and actuating selective ones of the data switches in the replacement set to replace one of the 2ⁿ−1 outputs of the shuffle exchange network with the 2^nth output of the shuffle exchange network.

[0007] This invention features a 2ⁿ−1 network including a shuffle exchange network for receiving 2ⁿ−1 data inputs and a dummy input providing 2ⁿ outputs. A replacement set of 2ⁿ−1 data switches receives 2ⁿ−1 outputs from the shuffle exchange network. A selection circuit actuates selective ones of the 2ⁿ−1 data switches in the replacement set to replace one of the 2ⁿ−1 outputs of the shuffle exchange network with a 2^nth output of the shuffle exchange network.

[0008] In a preferred embodiment the shuffle exchange network may include at least one set of shuffle data switches. Each set of shuffle data switches may include at least 2ⁿ data switches. There may be n sets of shuffle data switches. There may be 2ⁿ data switches in each set of shuffle data switches. Each data switch in the replacement set of data switches may include a 2 to 1 multiplexer. Each data switch in the set of shuffle data switches may include a 2 to 1 multiplexer. The shuffle exchange network may include a coding circuit for selectively actuating the sets of data switches in the set of shuffle data switches. The coding circuit may actuate each set of shuffle data switches independently. It may actuate all of the data switches in a set of shuffle data switches together. The coding circuit may include a sequence generator for providing each data input at the data output only once each sequence cycle. The sequence generator may include a pseudo random number generator.

[0015] There is shown in FIG. 1 a typical segmented digital to analog converter circuit 10 having a unary input 12 and a binary input 14. The unary inputs are derived from the binary thermometer decoder 16. Binary thermometer decoder 16 receives n inputs at input 18 from an input signal which includes m+n inputs on line 20. The remaining m inputs are delivered on line 22 to the binary input 14 of DAC 10. m may typically be smaller than n but not necessarily. Binary thermometer decoder 16 receives the n inputs on line 18 that produces 2ⁿ−1 outputs on line 24 to the 2ⁿ−1 shuffling network 26. One more input, the dummy input D, is provided on line 28 to 2ⁿ−1 shuffling network 26. The dummy input 28 may typically be a simple fixed or reference signal which may be high or low or zero. The output of 2ⁿ−1 shuffling network 26 is delivered on line 30 to the unary input 12. While, in the embodiment described hereinafter, binary input 14 includes m inputs, this is not a necessary limitation of the invention. Input 14 may be a unary array or a sub-unary array or any other type of array. Also for purposes of further explanation herein n is 3 and m could be 3 as well.

[0016] In prior art shuffling networks 26a, FIG. 2 there is a shuffle exchange network 40 consisting of n sets, in this case three sets, 42, 44, and 46 of data switches 48 of which there are 2^nth or eight in the specific embodiment where n is 3 in each set. The 2^nth inputs are labeled A–H. The outputs are S–Z. Also included in shuffling network 26a is a coding circuit 50. In prior art devices coding circuit 50 has three groups, 52, 54, and 56 of eight lines each so that each of the eight data switches 48 in each of the sets 42, 44, and 46 can be operated independently.

[0017] In the realization of this invention it was understood that if, instead of independent operation, all of the data switches within each set were operated globally, together, the input output transform would appear as shown in the 2ⁿ through path mapping table, FIG. 3. There it can be seen that coding circuit 50 provides eight coded inputs, numbered 1–8 and in response thereto shuffles the inputs A–H so that they appear in different combinations at the outputs S–Z. For example, with code 1 the inputs appear in the order A, B, C, D, E, F, G, H, at outputs S–Z, respectively. In response to code 2 the inputs appear in the order BADCFEHG at the outputs S–Z, respectively, and so on.

[0018] If such a prior art shuffle network 26a were used in place of 2ⁿ−1 shuffling network, FIG. 1, according to this invention, 2ⁿ inputs would produce 2ⁿ outputs, not 2ⁿ−1 outputs. This would cause redundant data and loss of data. In accordance with this invention it was realized that to convert from a 2ⁿ input to a 2ⁿ−1 output, it would be necessary simply to eliminate an output, for example, output Z so that the right-hand most column 60 in FIG. 3 would simply be eliminated. This would of course eliminate all of the data in that column as well, contributing to inaccuracy in the transformation or shuffling. In addition, one of the inputs would be redundant. For example, arbitrarily picking H as the redundant or dummy input, one can see that in each of the outputs S–Y in FIG. 3, throughout the sequence of codes 1–8, the input H appears but the input H is a dummy so no information is contributed by that input. In addition the true inputs A–G that could contribute to the accuracy of the transformation or shuffling have been eliminated with the elimination of output Z, column 60. This invention realizes that each of the occurrences of input H, now a dummy, could be replaced with the real input data which has been eliminated by the elimination of column 60. For example, at code 2 where input H appears at output Y, input G could be substituted. At code 3 where input H appears at X, input F could be substituted. And at code 4 where input H appears at output W, input E could be substituted, and so on through code 8 where input H appears at output S and could be replaced with input A from column 60.

[0019] In accordance with the realization of this invention, the 2ⁿ−1 shuffling network 26b, FIG. 4 can be implemented so that there are 2ⁿ−1 inputs and 2ⁿ−1 outputs. In 2ⁿ−1 shuffling network 26b, shuffle exchange network 40b still includes n sets 42b, 44b, and 46b of 2ⁿ data switches 48 in each set. But now instead of input H, dummy input 70 occurs and a replacement set 72 of data switches 76 has been added at the output of set 46b. And a selection circuit 74 has been added to individually control each of the 2ⁿ−1 data switches 76 in set 72.

[0020] In shuffle exchange network 40b, FIG. 4 lines 52b, 54b, and 56b are single lines which operate all of the data switches 48 in each set 42b, 44b, and 46b together, globally, while a coding circuit 50b operates each of the sets independently.

[0021] In operation, selection circuit 74 actually includes 2ⁿ−1, or in this particular case seven lines, one output to each of the data switches 76 in replacement set 72. Coding circuit 50b provides an output on each of lines 52b, 54b, and 56b to selection circuit 74 so that selection circuit 74 is always aware of which coding step, 1–8, FIG. 5, is being currently imposed on shuffle exchange network 40b. In this way selection circuit 74 knows each time an H would appear on a particular data switch 76 in data set 72 and instead replaces that with the inputs A–G from the eliminated column 60 of output Z, which are derived from inputs A–G through the shuffle exchange network 40b and appear on line 78 coincidentally with the actuation of the particular one of data switches 76 that otherwise would be subject to the redundant input H.

[0022] Now it can be seen that the transform is indeed from 2ⁿ−1 inputs to 2ⁿ−1 outputs and the eight codes in the mapping table of FIG. 5 provide, for each output S–Y, a unique set of inputs A–H. However, there is a duplicated input set. For example, output S includes two inputs A, output T includes two inputs B, output U includes two inputs C, output V includes two inputs D, output W includes two inputs E, output X includes two outputs F, and output Y includes two inputs G. While this is tolerable, even better accuracy can be obtained by removing that redundancy. This can be done, in this particular embodiment, by eliminating code 1, 000 and thereby removing A, B, C, D, E, F, and G coincident with coding 1. This can be done by a sequence generator which provides each data input at the data output only once for each sequence cycle. One sequence generator that works well is a pseudo random number generator which inherently can not produce an all zero output and so automatically eliminates that code.

[0023] Another advantage of this invention is that in the implementation shown in FIG. 4, the data switches 48b and 76 can be implemented very simply with a 2 to 1 multiplexer. Although a specific cross point connected shuffling exchange network has been shown, FIG. 4, this is not a necessary limitation of the invention as any desired cross point connection can be used: a local switching or decision making type or a benes, omega, or clos type. This will change the through path on the mapping table, FIG. 5, but the invention still applies. Similarly the coding circuit 50b need not be a pseudo random number generator, it could be simply a register that counts around but does not produce the number 000. Although this embodiment has been disclosed with n=3, this is not a necessary limitation of the invention and in fact the invention's usefulness is proportional to the increase in the size of n; for example, good results have been obtained with an n=7 or greater. Also, although the H input was chosen as the redundant quantity to be made a dummy input, this is not a limitation of the invention. Any of the other inputs A–G could have been used. Further, there is no restriction in the example of having eliminated the output Z as any of the other outputs S–Y could have been eliminated.

[0024] Although specific features of the invention are shown in some drawings and not in others, this is for convenience only as each feature may be combined with any or all of the other features in accordance with the invention. The words “including”, “comprising”, “having”, and “with” as used herein are to be interpreted broadly and comprehensively and are not limited to any physical interconnection. Moreover, any embodiments disclosed in the subject application are not to be taken as the only possible embodiments.

[0025] Other embodiments will occur to those skilled in the art and are within the following claims.