Browse Prior Art Database

Variable-Width Rotation Scheme for Interleaving

IP.com Disclosure Number: IPCOM000038686D
Original Publication Date: 1987-Feb-01
Included in the Prior Art Database: 2005-Jan-31
Document File: 2 page(s) / 37K

Publishing Venue

IBM

Related People

McAuliffe, KP: AUTHOR [+2]

Abstract

A method is described herein for effecting a variable-amount right rotate of a variable-width bit-field to support a data interleaving function. The method uses less hardware than a crossbar switch to perform the interleave function. The objective of the method presented is to replace the variable-width rotate with a fixed-width logical shift; the number of bit positions shifted is still a variable amount. Let an address to be interleaved be defined as having a node number field of n bits and a storage offset of m bits, as shown in Fig. 1. Let the bits in the node number be labeled HSn-1 to HSO, where HSn-1 is the most significant bit (MSB). Let the storage offset bits be labeled LSm-1 to LSO similarly. The maximum interleave amount for the address (in Fig. 1) is n.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

Variable-Width Rotation Scheme for Interleaving

A method is described herein for effecting a variable-amount right rotate of a variable-width bit-field to support a data interleaving function. The method uses less hardware than a crossbar switch to perform the interleave function. The objective of the method presented is to replace the variable-width rotate with a fixed-width logical shift; the number of bit positions shifted is still a variable amount. Let an address to be interleaved be defined as having a node number field of n bits and a storage offset of m bits, as shown in Fig. 1. Let the bits in the node number be labeled HSn-1 to HSO, where HSn-1 is the most significant bit (MSB). Let the storage offset bits be labeled LSm-1 to LSO similarly. The maximum interleave amount for the address (in Fig. 1) is n. The functional operation of the variable-amount right rotate on the variable-width bit-field for an interleave amount of q (O<=q<=n) is as follows: bits HSq-1 to LSO are rotated to the right q bit positions. The n-q MSBs of the node number are unchanged. Since q can range from O to n, the total number of bits that are rotated is variable. This varying-width bit-field makes it difficult to design a logic function to perform the rotate. Thus a method has been developed that is functionally equivalent to the rotate, but performs a logical shift on a fixed-size field. Prior to performing the fixed-length shift a variable-width replacement is needed. The variable-width replacement is composed of a set of 2-to-1 multiplexers. The number of multiplexers is equal to the maximum width of the variable-width bit- field. For example, the node number in Fig. 1 could be replaced by bits LSn-1 to LSO. In this case the number of multiplexers needed to perform the replacem...