N-bit wide parallel rotation algorithm

Claim 2

A circuit for rotating an x scanline by y bit image grouped into m-bit words comprising: a first shifter for circularly shifting each word by n bits times the scanline number mod n, where n is a fraction of m, a first buffer means implemented from m/n memory devices, numbered 1 to m/n, each device n-bits wide, for storing the words shifted by said first shifter, a system of connecting lines for reordering the output bits of said first buffer means so that when the bits are read out of the first buffer in the following order:

Claim 3

1, . . . n-1 from memory device 1; 1 0, 1, . . . n-1 from memory device 2; . . . to memory device m/n ##EQU1## they will be reordered into the following order: ##EQU2## a second shifter for grouping said bits received from said connecting lines into m bit words, numbering said m bit words from zero, and circularly shifting each m bit word received from said connecting lines by n bits times the m bit word number, mod n, a second buffer means implemented from m/n memory devices, each device n-bits wide, for storing the output of said second shifter, and a third shifter for receiving and circularly shifting each word received from said second buffer means by n bits times the third shifter scanline number mod n, the result being the fully rotated image.

Claim 4

1, . . . n-1 from memory device 1; 1 0, 1, . . . n-1 from memory device 2; . . . to memory device m/n ##EQU1## they will be reordered into the following order: ##EQU2## a second shifter for grouping said bits received from said connecting lines into m bit words, numbering said m bit words from zero, and circularly shifting each m bit word received from said connecting lines by n bits times the m bit word number, mod n, a second buffer means implemented from m/n memory devices, each device n-bits wide, for storing the output of said second shifter, and a third shifter for receiving and circularly shifting each word received from said second buffer means by n bits times the third shifter scanline number mod n, the result being the fully rotated image.

Claim 5

A circuit for rotating an x scanline by y bit image grouped into m bit words comprising: a first shifter for circularly shifting each word by n bits times the scanline number, mod n, where n is a fraction of m, a first buffer means implemented from m/n memory devices, numbered 1 to m/n, each device n-bits wide, for storing the result of said shifting of said first shifter, a second shifter for receiving said shifted words from said first buffer, numbering said shifted words from zero to generate numbered m circularly shifting each numbered m bit word received from said first buffer means by n bits times the m bit word number, mod n a system of connecting lines for reordering the output bits of said second shifter so that when the bits are read out of the second shifter in the following order: 0, 1, . . . n-1 0 from memory device 1; 0, 1, . . . n-1 1 from the memory device 2; . . . to memory device m/n ##EQU3## they will be reordered into the following order: ##EQU4## a second buffer means implemented from m/n memory devices, each device n-bits wide, for storing the output of said connecting lines, and a third shifter for reading out the image data from said second buffer means and for circularly shifting each word received from said second buffer means by n bits times the third shifter scanline number, mod n, the result being the fully rotated image.

Claim 6

A circuit for rotating an x scanline by y bit image grouped into m bit words comprising: a first shifter for circularly shifting each word by n bits times the scanline number, mod n, where n is a fraction of m, a first buffer means implemented from m/n memory devices, numbered 1 to m/n, each device n-bits wide, for storing the result of said shifting of said first shifter, a second shifter for receiving said shifted words from said first buffer, numbering said shifted words from zero to generate numbered m circularly shifting each numbered m bit word received from said first buffer means by n bits times the m bit word number, mod n a system of connecting lines for reordering the output bits of said second shifter so that when the bits are read out of the second shifter in the following order: 0, 1, . . . n-1 0 from memory device 1; 0, 1, . . . n-1 1 from the memory device 2; . . . to memory device m/n ##EQU3## they will be reordered into the following order: ##EQU4## a second buffer means implemented from m/n memory devices, each device n-bits wide, for storing the output of said connecting lines, and a third shifter for reading out the image data from said second buffer means and for circularly shifting each word received from said second buffer means by n bits times the third shifter scanline number, mod n, the result being the fully rotated image.