Teleputers LLC

+--------------- I did some searching to find out more about the algorithm for setting up a transpose (basically, the two outer layers divide the bits into two halves; if you can get the bits into two matching halves, then you just repeat the trick working inwards), and I stumbled upon a *patent*, only about a year old, for adding that instruction to a computer! It is held by a company called Teleputers, to which it was buttigned, the founder of that company being one of the inventors. The patent notes specifically that this kind of instruction is useful for implementing encryption algorithms. (Also, someone has patented the use of a Benes network to provide a variable bit transpose in a block cipher, as it happens, as well.) +---------------

For prior art which might invalidate this, you might look for a really, really old chip that AMD used to make in the late 1980's my apologies that I don't remember the part number that did a 32-word-32-bit transposition. As best I recall, there was a 32-bit data bus, 5 address lines, a clock, an output enable, and a "rotate" (or not) control line. You basically treated the thing as a 32x32 register file that could be viewed either in "normal or "rotated" mode. That is, you could store 32 (or fewer) 32-bit words, then read out the same data, but bit-transposed. The main intended use was for laser printers, to provide fast 90-degree rotation of bit-mapped fonts.

Also see:

"Method for rotating a binary image" buttignee: International Business Machines Corporation (Armonk, NY)

"Programmable interconnection chip for computer system functional modules" buttignee: Carnegie-Mellon University (Pittsburgh, PA) ... FIG. 8 is a schematic view showing how the chip of the present invention can be utilized to transpose a large matrix. ... 4. Application Examples Corner Turning ... The corner turning operation is like matrix transposition. For example, it may be necessary to transpose an input matrix in column-major ordering to an output in row-major ordering. Such a corner turning operation is illustrated in FIG. 7a. ...

-Rob

----- San Mateo, CA 94403 (650)572-2607