Electrical computers and digital processing systems: processing – Byte-word rearranging – bit-field insertion or extraction,...
Reexamination Certificate
1999-03-08
2001-06-05
Kim, Kenneth S. (Department: 2183)
Electrical computers and digital processing systems: processing
Byte-word rearranging, bit-field insertion or extraction,...
C708S204000
Reexamination Certificate
active
06243808
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of The Invention
The present invention relates to the process of bit, byte and word swapping, and particularly to implementing processor functions by swapping bits, bytes and words.
2. State of The Art
In a digital processing system, functions or operations are performed on digital words by manipulating or swapping the bits (single bit), nibbles (4-bits), bytes (8-bits), or half words (16-bits) of a digital word. For instance, a well known operation performed within processing systems is changing the format of a digital word from a big endian format to a little endian format. In particular, a digital word in a big endian format has its least significant bit starting from the highest order address of the word. A word in a little endian format has its least significant bit starting from the lowest order address of the word. Often times when interfacing between processing systems, bit swapping is required to accommodate the particular endian format of the system receiving or sending the data. Swapping might also be performed for other operations within the processing system such as a bit field extraction or a Viterbi operation.
In general, the manner in which swapping was previously performed was to design a system that is hardwired to perform only one particular swapping pattern. For instance, a hardwired system might be designed to exclusively perform a big endian to little endian bit swapping operation. However, providing hardware circuitry for performing swapping in this manner can result in a significant amount of additional hardware depending on the amount and type of swapping required in the system. Another typical prior art swapping design technique utilizes large multiplexers having many inputs which are controlled with complex control signaling resulting in significant space and power usage. Alternatively, swapping has been performed by a sequence of digital signal processing (DSP) steps such as shifting, masking, and storing. The disadvantage of performing swapping in this manner is that it can tie up valuable processing cycles retrieving and loading data and, in general, can take many processing cycles to accomplish.
The present invention is an apparatus and system that is programmable to perform any random bit, nibble, byte, and half word swap utilizing simplified multiplexer circuitry and minimal control signaling thereby obviating hardwired swapping systems, complex high-power multiplexer systems, and DSP swapping techniques.
SUMMARY OF THE INVENTION
An apparatus and method of performing random bit swapping of a digital word (e.g., bit (single bit) swap, nibble (4-bit) swap, byte (8-bit) swap, and half word (16-bit) swap). The apparatus includes a matrix or array of means for signal path selection for selecting between a “non-swapped” bit value and a “swapped” bit value. In one embodiment, the selection means is a multiplexer. The matrix of selection means are arranged into rows and all selection means in a given row are coupled to the same control line such that all of the selection means in a given row pass either the “non-swapped” bit value when controlled by a first control signal or all of the selection means pass the “swapped” bit value when controlled by a second control signal. In addition, the selection means in each row are grouped such that the “non-swapped” and “swapped” bit values coupled to each selection means' inputs in a given group originates from within the given group. In one embodiment, the group sizes of the selection means progressively increases from the first row to the last row. In one embodiment, the group size for the first row is two selection means per group and the group size increases to 2
n
for subsequent rows n=2, 3, . . . N, where N is the total number of rows and n is the row number. In one embodiment, the number of bits in the word being operated on, m, is equal to 2
N
and the number of bits m in the word corresponds to the number of selection means in each row.
In one embodiment of an apparatus for performing swapping of an 8-bit data word, the matrix includes three rows of eight two-to-one multiplexers. The first row includes four groups of two adjacent two-to-one multiplexers. The second row includes two groups of four adjacent multiplexers and the third row includes one group of eight adjacent multiplexers. Each multiplexer in each group of the first row has its first input coupled to a “non-swapped” bit value having an associated bit location that corresponds to the location of the multiplexer within the row and has its second input coupled to a “swapped” bit value which corresponds to the bit value of the adjacent multiplexer in the group. Each multiplexer in each group of the remaining two rows has its first input coupled to a “non-swapped” bit value received from the previous (i.e., first) row and having an associated bit location that corresponds to the location of the multiplexer within the row and has its second input coupled to a “swapped” bit value having an associated bit location that is symmetrically opposite to the “nonswapped” bit value location within the group. The matrix is controlled by three control lines, each row having an associated single control line such that the select input of each multiplexer in a given row is coupled to that single control line.
In one embodiment the three row—eight two-to-one multiplexer matrix is controlled such that the first row selects the “non-swapped” bit value, the second row selects the “non-swapped” bit value, and the third row selects the “swapped” bit value resulting in a complete bit reverse of the 8-bit input word. This type of swapping operation corresponds to a Fast Fourier Transform (FFT) operation.
In a second embodiment the three row—eight two-to-one multiplexer matrix is controlled such that the first row selects the “non-swapped” bit value, the second row selects the “swapped” bit value, and the third row selects the “swapped” bit value resulting in a nibble swap of the 8-bit input word. This type of swapping operation corresponds to a big endian/little endian transformation operation.
In a third embodiment the three row—eight two-to-one multiplexer matrix is controlled such that the first row selects the “swapped” bit value, the second row selects the “non-swapped” bit value, and the third row selects the “swapped” bit value resulting in a 2-bit swap of the 8-bit input word.
REFERENCES:
patent: 5265259 (1993-11-01), Satou et al.
patent: 5524256 (1996-06-01), Turkowski
patent: 5819117 (1998-10-01), Hansen
patent: 5948099 (1999-09-01), Crawford et al.
patent: 6078937 (2000-06-01), Vatinel
Burns Doane , Swecker, Mathis LLP
Chameleon Systems, Inc.
Kim Kenneth S.
LandOfFree
Digital data bit order conversion using universal switch... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Digital data bit order conversion using universal switch..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Digital data bit order conversion using universal switch... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2468825