Priority encoder circuit

Details Priority encoder circuit Priority encoder circuit

1997-12-15

2001-01-02

Sheikh, Ayaz R. (Department: 2781)

Electrical computers and digital data processing systems: input/

Access arbitrating

Access prioritizing

C710S240000, C710S241000, C710S243000

Utility Patent

active

06170032

ABSTRACT:

FIELD OF THE INVENTION
The present invention is directed generally to electronic circuits, and more specifically, to an improved priority encoder circuit.
BACKGROUND OF THE INVENTION
A priority encoder circuit is a logic circuit that is used to receive a number of inputs carrying binary signals, each input having a predetermined priority, and to determine the input with the highest priority carrying a predetermined binary signal. For example, a computer may have several peripheral devices attached to a single input/output port, such as a compact disk read-only memory (“CD ROM”) drive, a floppy disk drive, and a tape reader. A priority encoder circuit having three inputs could be used in this application to receive three binary signal inputs, one from each peripheral device, which represent requests for access. The priority encoder circuit generates a binary output signal, such as one, that represents the highest priority input receiving a predetermined binary signal corresponding to a request for access. Input/output port access would then be given to the corresponding device with the highest priority that is requesting access.
For example, if priority was assigned on the basis of data transfer speed, the CD ROM drive would have the highest priority, followed by the floppy disk drive and the tape reader. The priority encoder circuit input coupled to the CD ROM drive would therefore have the highest priority, followed by the inputs coupled to the floppy disk drive and the tape drive, respectively. If the priority encoder circuit inputs indicated that access to the input/output port was requested by all three devices, then the priority encoder circuit would receive three signals representative of a binary one, and would generate an output that indicates that input/output port access should be given to the CD ROM drive. This is typically accomplished by converting the inputs (the “request vector”) into outputs (the “grant vector”) having a binary value equal to the priority ranking of the highest priority device requesting access.
Thus, request vector inputs to a priority encoder circuit of “1 1 1,” “1 1 0,” and “1 0 0” (corresponding to a CD ROM drive, a floppy disk drive, and a tape drive request bit) would each yield a grant vector output from the priority encoder circuit of “0 1,” where the grant vector contains the binary value for “one,” indicating a grant of priority to the device associated with the first bit in the request vector string, i.e., the CD ROM drive. Likewise, request vector inputs of “0 1 1” and “0 1 0” would yield grant vector outputs of “1 0,” the binary value for “two,” indicating a grant of priority to the device associated with the second bit in the request vector string, i.e., the floppy disk drive. A request vector input of “0 0 1” would yield a grant vector output of “1 1,” the binary value for “three,” indicating a grant of priority to the device associated with the third bit in the request vector string, i.e., the tape drive.
Several problems have been encountered with priority encoder circuits operating on this principle. One problem is that many logic gate devices must be used to implement the priority encoder circuit. In general, the number of logic devices required to implement known priority encoder circuits increases exponentially with the number of inputs to the priority encoder circuit. Another problem is that the top position, the peripheral device having the highest priority in the preceding example, must remain fixed. If all peripheral devices have the same priority, it is not possible to change the top position in a known priority encoder circuit to ensure that all peripheral devices will get equal access to the input/output port over time.
SUMMARY OF THE INVENTION
Therefore, a need has arisen for a priority encoder circuit that substantially eliminates or reduces the problems associated with known priority encoder circuits.
In particular, a priority encoder circuit is required in which the number of logic devices that must be used to implement the priority encoder circuit does not increase exponentially with the number of inputs, and in which the top position of the request vector is not fixed.
According to one embodiment of the present invention, a priority encoder circuit is provided that includes a plurality of inputs and outputs. The number of inputs equals the number of outputs, and each input corresponds to one output. Each input receives a signal that indicates whether the input has been selected. The priority encoder circuit also includes circuitry that generates a signal at the output corresponding to the input having the highest priority that receives the selection signal.
One important technical advantage of the present invention is that the priority encoder circuit of the present invention may be implemented with a number of logic devices that increases linearly with the number of inputs to the priority encoder circuit.
Another technical advantage of the present invention is a priority encoder circuit that allows the input having the top priority position to be controllably changed, so as to allow more than one input to have top priority over time.


REFERENCES:
patent: 3921145 (1975-11-01), Emm et al.
patent: 4348741 (1982-09-01), McAlister et al.
patent: 5095460 (1992-03-01), Rodeheffer
patent: 5267235 (1993-11-01), Thacker
patent: 5623672 (1997-04-01), Popat
patent: 5896539 (1999-04-01), Arimilli et al.
“A Quantitative Comparison of Scheduling Algorithms for Input-Queued Switches*,” McKeown, et al., pp. 1-16.
“Achieving 100% Throughput in an Input-Queued Switch,” McKeown, et. al., Proceedings of IEEE Infocom '96, vol. 3 Mar. 1996, pp. 296-302.
“Current Integrating Receivers for High Speed System Interconnects”, Sidiropoulos, et. al., IEEE Custom Integrated Circuits Conference, May 1995, pp.
“Data Structures and Network Algorithms”, R.E. Tarjan,Society for Industrial and Applied Mathematics, Pennsylvania, Nov. 1993, pp.
“High Performance Multi-Queue Buffers for VLSI Communication Switches”, Tamir, et. al., Proc. of 15thAnnual Symposium on Comp. Arch., Jun. 1988, pp. 343-354.
“High Speed Switch Scheduling for Local Area Networks”, Anderson, et. al., ACM Trans.On Computer Systems, Nov. 1993, pp. 319-352.
“Input Versus Output Queueing on a Space Division Switch”, Karol, et. al.,IEEE Trans. Communications, 35(12) 1987, pp. 1347-1356.
“Precise Delay Generation Using Coupled Oscillators”, John Maneatis,IEEE Journal of Solid State Circuits, vol. 28, No. 12, Dec. 1993, pp.
“Scheduling Cells in Input-Queued Cell Switches”, Nick McKeown, PHD. Thesis, University of California, Berkley, 1995, pp.
“Scheduling Cells in an Input-Queued Switch”, McKeown, et. al.,IEE Electronics Letters, Dec. 1993, pp. 2174-2175.
“Scheduling Multicast Cells in an Input-Queued Switch”, Proceedings of IEEE Infocom '96, vol. 3, Mar. 1996, pp. 271-278.
“Multicast Scheduling for Input-Queued Switches”, Prabhaker, et al.,IEEE Journal on Selected Areas in Communications, vol. 15, No. 5, Jun. 1997, pp. 855-866.

Affiliated with

Also associated with

Rating

Priority encoder circuit does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Priority encoder circuit, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Priority encoder circuit will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2476031