Browse Prior Art Database

A Method for Generating the Residue of Bits Shifted out of a Shifter

IP.com Disclosure Number: IPCOM000109047D
Original Publication Date: 1992-May-01
Included in the Prior Art Database: 2005-Mar-23
Document File: 1 page(s) / 58K

Publishing Venue

IBM

Related People

Faget, RR: AUTHOR [+2]

Abstract

A method for generating the MOD 3 residue value of the bits shifted out of a shifter is disclosed. This method generates the residue of each field of the input data that might be lost during the shift operation and selects the correct field's residue using bits in the shift amount.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 73% of the total text.

A Method for Generating the Residue of Bits Shifted out of a Shifter

      A method for generating the MOD 3 residue value of the bits
shifted out of a shifter is disclosed.  This method generates the
residue of each field of the input data that might be lost during the
shift operation and selects the correct field's residue using bits in
the shift amount.

      Because residue is generated in a tree-like structure, the
smaller fields' residues will come out earlier than the larger
fields' residues, and selection of the proper residue can be done in
parallel with much of the residue generation (see the figure).

      The overall complexity and fan-out requirements of an apparatus
that generates residues for all fields of the input data that may be
discarded can quickly become difficult to manage.  This problem can
be solved by breaking the residue generation up into 2 trees.  The
primary tree generates residue on all the fields that could be
shifted out of the first n levels of shifting.  A secondary residue
generation tree, using data from the nth level of the shifter,
generates the residue of all the fields that could be discarded from
the nth level of the shifter on.  The residue from the secondary
residue generation tree, added to the residue from the primary
residue generation tree, gives the residue of the bits shifted out of
the shifter.  In general, this concept can be used on any size
shifter to break up the residue generation problem into 2 or...