System for rearranging sequential data words from an initial order to an arrival order in a predetermined order

Abstract

A data shuffler of the pipeline type receives successive trains of n sequential data words and rearranges data words in each train according to a predetermined order. It comprises p (p≦n) elementary processing units arranged in series. Each unit comprises an input, an output, a one-word storage register (20), a steering means (21) in order, in response to a binary control, to connect the input to the output either directly or through the register; and means for periodically supplying to each of the p steering means a sequence of n control bits determined as a function of said predetermined order.

I claim: 
     
       1. A pipeline data shuffler receiving successive trains of sequential data words, and rearranging said sequential data words in each said train according to a predetermined order comprising: a plurality of elementary processing units arranged and connected in series, each said elementary processing unit comprising:   an input;   an output;   a one-word storage register for temporarily storing one of said data words receiving from said input;   steering means for controlling the elementary processing unit to connect the input to the output through the register for temporarily storing the data word in response to a first level of a control signal and for connecting the input directly to the output thereby bypassing the register in response to a second level of the control signal; and   means, coupled to each said elementary processing unit, for periodically and concurrently supplying to each of the steering means of each said elementary processing unit a sequence of said control signals based upon a number of sequential data words in said each train and determined as a function of said predetermined order to rearrange the sequential data words.   
     
     
       2. A data shuffler according to claim 1, wherein, when successive elementary units are controlled by identical sequences, the steering means which separate them are suppressed. 
     
     
       3. A data shuffler according to claim 1, wherein a number of the elementary processing units is not more than a number of the sequential data words in each of the successive trains. 
     
     
       4. A data shuffler according to claim 1, wherein a number of the control signals is equal to a number of the sequential data words in each of the successive trains. .Iadd. 
     
     
       5.  A method of rearranging sequential data from a predetermined initial order in which a first datum appears before a second datum to a predetermined arrival order in which the second datum appears before the first datum, comprising the steps of: passing the data through a series of registers each having an input and an output, the registers connected in series; and   selectively bypassing the second datum from the input of a register of the series to the output of the register of the series while the first datum is held in the register, so the second datum appears in the arrival order before the first datum. .Iaddend..Iadd.6. The method of claim 5, wherein the steps of passing and selectively bypassing are repeated until the arrival order is achieved. .Iaddend..Iadd.7. A data shuffler for rearranging sequential data from a predetermined initial order to a predetermined arrival order, comprising:   a plurality of registers, each of a size to hold one datum, and each having an input and an output;   at least one selector having two inputs and one output, one of the inputs connected to the output of one of the registers to receive a datum stored therein, another of the inputs connected to the input of the one of the registers to receive a datum not stored in the one of the registers and the output connected to the input of another of the registers; and   a selector control including a control store representing a mapping of the predetermined initial order to the predetermined arrival order as a plurality of binary commands to control the selector so as to determine when the output of the selector represents the datum present at the one input and when the output of the selector represents the datum present at   
     
     
        the other input. .Iaddend..Iadd.8.  The method of claim 5, wherein the predetermined initial order and the predetermined arrival order each include a predetermined number of data words, the method further comprising the steps of: storing for each register of the series of registers a sequence of commands equal in number to the predetermined number of data words;   determining for each data word whether the data word is selectively bypassed based on a value of corresponding command. .Iaddend..Iadd.9. A method of rearranging sequential data from a predetermined initial order in which a first datum appears before a second datum to a predetermined arrival order in which the second datum appears before the first datum, comprising the steps of:   passing the data through a register having an input and an output; and   selectively bypassing the second datum from the input of the register to the output of the register while the first datum is held in the register, so the second datum appears in the arrival order before the first datum. .Iaddend..Iadd.10. The method of claim 9, wherein the steps of passing and selectively bypassing are repeated until the arrival order is achieved.   
     
     
        .Iaddend..Iadd.11.  The method of claim 9, wherein the predetermined initial order and the predetermined arrival order each include a predetermined number of data words, the method further comprising the steps of: storing for the register a sequence of commands equal in number to the predetermined number of data words;   determining for each data word whether the data word is selectively bypassed based on a value of a command corresponding to a position of the data word within the predetermined initial order. .Iaddend..Iadd.12. The method of claim 11, the predetermined initial order and the predetermined arrival order each including a predetermined number of data, wherein the sequence of commands is a number of bits equal to the predetermined number of data, each bit designating which input of the selector is represented at the output upon arrival at the selector of datum whose position within the predetermined initial order corresponds to each bit. .Iaddend..Iadd.13. A method of rearranging a serial input sequence of a predetermined number of data having a predetermined initial order, producing a serial output sequence of the predetermined number of data having a predetermined sorted order, the method comprising the step of:   precalculating a sequence of commands equal in number to the predetermined number of data, the precalculated commands defining rearrangements of pairs of data such that when in the initial order a first datum is in a position before a second datum and in the sorted order the second datum is in a sorted position before the first datum a command in the sequence of commands corresponding to the first datum defines delaying output of the   
     
     
        first datum while the second datum is output. .Iaddend..Iadd.14.  The method of claim 13, further comprising the steps of: applying the serial input sequence to an input of a selectable delay element;   selecting to pass data of the serial input sequence applied to the input of the selectable delay element directly to an output thereof in accordance with a command of the sequence commands corresponding to the position of each datum in the serial input sequence. .Iaddend..Iadd.15. The method of claim 13, wherein the step of applying further comprises the steps of:   providing a predetermined number of selectable delay elements connected in series, the predetermined number equal to a greatest number of delays needed to rearrange data of the serial input sequence from positions of the data in the initial order to sorted positions of the data in the sorted order;   applying the serial input sequence to an input of one of the selectable delay elements; and   selecting to pass data of the serial input sequence applied to the input of the selectable delay element directly to an output thereof in accordance with commands of the sequence of commands corresponding to positions of the data in the serial input sequence. .Iaddend.