Logical shifting device and method of shifting

Claim 2

A logical shifting device capable of effecting a shifting operation to shift a binary word, comprising (N+1) bits, up to N places left or right including: a. a plurality of logical units at a first level and a further plurality of logical units at least at one further level; each level comprising a shift-left logical unit having logical gating stages with inputs interconnected through logical connections to the outputs of logical gating stages in the immediately preceding logical unit to produce a desired shift left in a respective portion of the binary word, a no-shift logical unit having logical gating stages with inputs interconnected through logical connections to the outputs of logical gating stages in the immediately preceding logical unit to pass the respective portion of the binary word therethrough with zero shift, and a shift-right logical unit with inputs interconnected through logical connections to the outputs of logical gating stages in the immediately preceding logical unit to produce a desired shift right in the respective portion of the binary word; b. control means for activating a selected one logical unit at each level for each shifting operation of the logical shifting device so that the desired magnitude and direction of shift is achieved at each level and the respective portion of said binary word is passed through one logical unit at each level during the shifting operation; whereby the total time taken by a shifting operation is constant for all such shifting operations.

Claim 3

A logical shifting device according to claim 1 having a first level and at least two further levels, wherein each level includes: a. a shift-left logical unit logically connected in the device to produce a desired shift left in the respective portion of said binary word; b. a no-shift logical unit logically connected in the device to pass the respective portion of said binary word therethrough with zero shift; and c. a shift-right logical unit logically connected in the device to produce a desired shift right in a respective portion of said binary word.

Claim 4

A logical shifting device according to claim 1 for effecting a shifting operation to shift a binary word, comprising 16 bits, up to 15 places left or right, including four levels wherein: a. the first level comprises: i. a shift-left logical unit having eight logical gating stages, ii. a no-shift logical unit having 16 logical gating stages, and iii. a shift-right logical unit having eight logical gating stages; b. the second level comprises: i. a shift-left logical unit having 12 logical gating stages and four cancelling gating stages, ii. a no-shift logical unit having 16 logical gating stages, and iii. a shift-right logical unit having 12 logical gating stages and four cancelling gating stages; c. the third level comprises: i. a shift-left logical unit having 14 logical gating stages, ii. a no-shift logical unit having 16 logical gating stages, and iii. a shift-right logical unit having 14 logical gating stages; and d. the fourth level comprises: i. a shift-left logical unit having 15 logical gating stages and one cancelling gating stage, ii. a no-shift logical unit having 16 logical gating stages, and iii. a shift-right logical unit having 15 logical gating stages and one cancelling gating stage.

Claim 5

A logical shifting device according to claim 3 wherein each of said logical gating stages is a logical NAND gate and the cancelling gating stages each comprise a single input gate capable of providing a zero output in response to an activating input.

Claim 6

A logical shifting device according to claim 1 wherein each logical gating stage is a logical NAND gate.

Claim 7

A logical shifting device capable of effecting a shifting operation to shift a binary word, comprising (N+1) bits, up to N places left or right including: a. a plurality of levels of logical units, each unit comprising a number of logical gating stages, the number of levels t being determined by the equation: 2t 1 <N+1 2t where t is the smallest integer which satisfies the equation, and in which: b. the logical units at each level after the first are logically connected to the logical units at the immediately preceding level; c. each level comprising a shift-left logical unit having logical gating stages with inputs interconnected through logical connections to the outputs of logical gating stages in the immediately preceding logical unit to produce a desired shift left in a respective portion of the binary word, a no-shift logical unit having logical gating stages with inputs interconnected through logical connections to the outputs of logical gating stages in the immediately preceding logical unit to pass the respective portion of the binary word therethrough with zero shift, and a shift-right logical unit with inputs interconnected through logical connections to the outputs of logical gating stages in the immediately preceding logical unit to produce a desired shift right in the respective portion of the binary word; d. the number of logical gating stages in the shift-left logical units at a particular level being dependent on the level whereby at the general (p) th level the number of logical stages is given by: Lp 2t-2t p; e. the number of logical gating stages in the no-shift logical unit being (N+1) for each level; f. the number of logical gating stages in the shift-right logical units being dependent on the level whereby at the general (p) th level the number of logical stages is given by: Rp 2t-2t p; and g. control means for activating a selected one logical unit at each level for each shifting operation of the logical shifting device so that the desired magnitude of shift is achieved and a respective portion of said binary word is passed through one logical unit at each level during the shifting operation; whereby the total time taken by a shifting operation is constant for all such shifting operations.

Claim 8

A logical shifting device capable of effecting a shifting operation to shift a binary word, comprising (N+1) bits, up to N places left or right including: a. a plurality of levels of logical units, each unit comprising a number of logical gating stages, the number of levels t being determined by the equation: 2t 1 <N+1 2t where t is the smallest integer which satisfies the equation, and in which: b. the logical units at each level after the first are logically connected to the logical units at the immediately preceding level; c. each level comprising a shift-left logical unit having logical gating stages with inputs interconnected through logical connections to the outputs of logical gating stages in the immediately preceding logical unit to produce a desired shift left in a respective portion of the binary word, a no-shift logical unit having logical gating stages with inputs interconnected through logical connections to the outputs of logical gating stages in the immediately preceding logical unit to pass the respective portion of the binary word therethrough with zero shift, and a shift-right logical unit with inputs interconnected through logical connections to the outputs of logical gating stages in the immediately preceding logical unit to produce a desired shift right in the respective portion of the binary word; d. the number of logical gating stages in the shift-left logical units at a particular level being dependent on the level whereby at the general (p) th level the number of logical stages is given by: Lp 2t-2t p; e. the number of logical gating stages in the no-shift logical unit being (N+1) for each level; f. the number of logical gating stages in the shift-right logical units being dependent on the level whereby at the general (p) th level the number of logical stages is given by: Rp 2t-2t p; and g. control means for activating a selected one logical unit at each level for each shifting operation of the logical shifting device so that the desired magnitude of shift is achieved and a respective portion of said binary word is passed through one logical unit at each level during the shifting operation; whereby the total time taken by a shifting operation is constant for all such shifting operations.

Claim 9

A logical shifting device according to claim 6 which is an off-the-end shifting device and in which: a. the shift-left logical unit and the shift-right logical unit at the second level and at every succeeding alternate level each include a number of cancelling gate stages; b. the number of said cancelling gate stages at a particular level being dependent on the level whereby at the (p) th level the number of cancelling gates in the shift-left logical unit is Lcp (Lp-Lp 1) cancelling gate stages, and the number of cancelling gates in the shift-right logical unit is Rcp (Rp-Rp 1) cancelling gate stages, where the (p-1) th level immediately precedes the (p) th level.

Claim 10

A logical shifting device according to claim 7 for effecting a shifting operation to shift a binary word, comprising 16 bits, up to 15 places left or right, including four levels wherein: a. the first level comprises: i. a shift-left logical unit having eight logical gating stages, ii. a no-shift logical unit having 16 logical gating stages, and iii. a shift-right logical unit having eight logical gating stages; b. the second level comprises: i. a shift-left logical unit having 12 logical gating stages and four cancelling gating stages, ii. a no-shift logical unit having 16 logical gating stages, and iii. a shift-right logical unit having 12 logical gating stages and four cancelling gating stages; c. the third level comprises: i. a shift-left logical unit having 14 logical gating stages, ii. a no-shift logical unit having 16 logical gating stages, and iii. a shift-right logical unit having 14 logical gating stages; and d. the fourth level comprises: i. a shift-left logical unit having 15 logical gating stages and one cancelling gating stage, ii. a no-shift logical unit having 16 logical gating stages, and iii. a shift-right logical unit having 15 logical gating stages and one cancelling gating stage.

Claim 11

A logical shifting device according to claim 6 wherein the total number of logical stages in each logical unit is (N+1) to provide an end-around shifting device in which those bits which do not appear in the output binary word are recirculated and reinserted in an end-around shifting operation.