Test Set for a Multibit Shifter Constructed with Multiplexers

Tokumi YOKOHIRA  Hiroyuki MICHINISHI  Takuji OKAMOTO  Yuji SUGIYAMA  

Publication
IEICE TRANSACTIONS (1976-1990)   Vol.E73    No.8    pp.1301-1309
Publication Date: 1990/08/25
Online ISSN: 
DOI: 
Print ISSN: 0000-0000
Type of Manuscript: Special Section PAPER (Special Issue on Fault-Tolerant Systems)
Category: 
Keyword: 


Full Text: PDF>>
Buy this Article


Summary: 
This paper considers a test set for a multibit shifter which can execute arbitrary bit length shifting/rotating operations. The multibit shifter consists of several stages of sub-shifters, each of which can shift/rotate its inputs by an arbitrary number of bits less than or equal to a predetermined constant. Outputs of one sub-shifter are shifted/rotated in the next sub-shifted. All of the sub-shifters have the same structure, and are constructed with multiplexers. Every sub-shirter is separately tested. All of the multiplexers in each sub-shifter are tested in parallel and exhaustively. A minimum test set for every sub-shifter can be obtained by the use of an algorithm which generates a Boolean 2pq matrix M such that any 2pp submatrix of M includes all bit patterns of length p, where p and q (pq) are the numbers of input lines in a multiplexer and those in a sub-shifter, respectively. A complete test set for the multibit shifter can be easily obtained as the union of minimum test sets for all sub-shifters.