Implementing a priority function using ripple chain logic

Details Implementing a priority function using ripple chain logic Implementing a priority function using ripple chain logic

1999-03-29

2001-04-10

Tokar, Michael (Department: 2819)

Electronic digital logic circuitry

Multifunctional or programmable

Having details of setting or programming of interconnections...

C326S105000

Reexamination Certificate

active

06215325

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field Of the Invention
The present invention relates to a priority function. More particularly, the present invention relates to a method and apparatus for implementing priority functions using ripple chain logic elements commonly found in programmable gate arrays.
2. The Background
A Field Programmable Gate Array, commonly referred to as an FPGA, is a well-known target technology for implementing digital circuit designs. An FPGA typically employs a mix of simple and complex structures or elements, including discrete logic gates, look-up tables, and arithmetic functions, which may be selectively connected to create a semi-custom implementation of a circuit design. To minimize implementation costs, many designers create their designs by associating a desired function with a specific structure. They may also optimize the design by using discrete logic components to reduce the number of specific structures required, obtaining a dense FPGA implementation if the group being optimized is very active, i.e., has few constants. If the design is not very active, optimization may be possible but may be constrained by the granularity of the structures offered by selected target technology. Hence, the design may only be optimized to the extent that the resulting optimized design may still be implemented using the structures provided by the target technology. If so, the implementation can be said to under-utilize the functionality offered by the structures in a selected FPGA, and is therefore larger and slower than other implementations.
One example of a circuit design feature that may be implemented using FPGA technology is a priority function. A priority function is used to select a signal from among a set of eligible signals, such as interrupt signals, according to a given priority scheme. One type of priority function, commonly known as a priority encoder, generates a binary coded output representing the position of the highest priority input signal among a set of active input signals. Another type of priority function, which is referred to as a priority to 1-hot recoder, generates an output equivalent to the position of the highest priority input signal among a set of active input signals.
Those of ordinary skill in the art will readily recognize that these priority functions may be used with a selector to select data received from more than one device. This enables data sent by more than one of the devices to be directed over a single channel or bus, which is connected to the output of the selector, in a sequential manner. Thus, a single data channel or bus may be used to transfer data from more than one device by coupling the output of a priority function to the selector inputs of the selector.
For example,
FIG. 1
is a block diagram of a priority encoder
10
coupled to an encoded selector
12
(sometimes referred to as an encoded multiplexer). Priority encoder
10
has N inputs
14
-
1
through
14
-N and n outputs
18
-
1
through
18
-n, where N=2
n
−1. Encoded selector
12
has N inputs
20
-
1
through
20
-N and n selector inputs
22
-
1
through
22
-n. The selector inputs
22
-
1
through
22
-n are coupled to set of n outputs
18
-
1
through
18
-n, respectively. Output
24
and inputs
20
-
1
through
20
-N are each x bits wide. Since priority encoder
10
has N inputs, it is capable of receiving N control signals from N different devices, such as devices
26
-
1
through
26
N.
Priority encoder
10
maps its inputs to a binary address. This enables priority encoder
10
to generate a binary coded output corresponding to an input that is receiving an active control signal from a device and which has the highest priority among a set of inputs that are receiving an active control signal. Thus, if more than one device asserts a control signal, priority encoder
10
generates a binary address that corresponds to the device that asserted one of the control signals and which has the highest priority among all active devices. Encoded selector
12
uses the address to select one of its inputs, which corresponds to the data lines of the device selected by priority encoder
10
. Thus, data from N different devices may be selected using the priority encoder and encoded selector circuit disclosed in FIG.
1
.
FIG. 2
is a block diagram illustrating a priority to 1-Hot recoder
30
(hereinafter referred to as a “recoder”) coupled to an unencoded selector
32
(sometimes referred to as an unencoded multiplexer). Recoder
30
has inputs
34
-
1
through
34
-N and outputs
36
-
1
through
36
-N. Unencoded selector
32
has inputs
38
-
1
through
38
-N; selector inputs
40
-
1
through
40
-N coupled to outputs
36
-
1
through
36
-N, respectively; and an output
42
. Output
42
and inputs
38
-
1
through
38
-N are each x bits wide. Since recoder
30
has N inputs, it is capable of receiving N control signals from N different devices, such as devices
46
-
1
through
46
-N.
It is commonly known to implement priority functions and selectors using look-up tables offered by an FPGA. However, such an approach may suffer from the density limitations discussed above. In addition, such an approach does not fully utilize other components typically offered in an FPGA, such as arithmetic functions, increasing the number of look-up tables that would have been otherwise reduced if other components were used. For example, the number of look-up tables required for implementing the circuit in
FIG. 1
requires 2
(n+1)
-n-1+(2
n
−1)× look-up tables, while the circuit in
FIG. 2
requires 2
(n+1)
+⅓(2
n
−1) x look-up tables.
Accordingly, a need exists for increasing the density of FPGA implementations of digital circuit designs that have priority functions and selectors.
SUMMARY OF THE INVENTION
A method and apparatus pertaining to a ripple-data function unit having a ripple function and a data function for use in a priority circuit is described. The ripple-data function unit may be used to implement a priority encoder or a priority to 1-HOT recoder simply by defining the ripple and data functions as Boolean functions representing the ripple and arithmetic characteristics of the priority circuit desired. For example, at least one instance of a ripple-data function unit may be used to define a priority encoder if each instance includes ripple and data functions equivalent to the ripple and arithmetic characteristics of the priority encoder. Similarly, at least one instance of ripple-data function unit may be used to define a priority to-1-HOT recoder if each instance includes ripple and data functions equivalent to the ripple and arithmetic characteristics of the priority to 1-HOT recoder. The ripple-data function units may be implemented using ripple chain logic elements commonly available in many programmable logic array technologies, such as in an FPGA or an equivalent programmable logic device, improving the density of the resulting implementation.


REFERENCES:
patent: 4168530 (1979-09-01), Gajski et al.
patent: 4556948 (1985-12-01), Mercy
patent: 4575812 (1986-03-01), Kloker et al.
patent: 4748583 (1988-05-01), Noll
patent: 4752905 (1988-06-01), Nakagawa et al.
patent: 4831577 (1989-05-01), Wei et al.
patent: 4843585 (1989-06-01), Williams
patent: 4849920 (1989-07-01), Simpson et al.
patent: 4887084 (1989-12-01), Yamaguchi
patent: 5010510 (1991-04-01), Nishimura et al.
patent: 5072419 (1991-12-01), Zyner
patent: 5243348 (1993-09-01), Jackson
patent: 5265258 (1993-11-01), Fiene et al.
patent: 5404323 (1995-04-01), Xu et al.
patent: 5463562 (1995-10-01), Theobald
patent: 5465335 (1995-11-01), Anderson
patent: 5467462 (1995-11-01), Toshiaki
patent: 5497845 (1996-03-01), Ferguson et al.
patent: 5504915 (1996-04-01), Rarick
patent: 5521837 (1996-05-01), Frankle et al.
patent: 5560007 (1996-09-01), Thai
patent: 5581756 (1996-12-01), Nakabayashi
patent: 5634056 (1997-05-01), Casotto
patent: 5764953 (1998-06-01), Collins et al.
Prasad, et al., “Using Parallel Data Structures in Optimistic Discrete Event Simul

Affiliated with

Also associated with

Rating

Implementing a priority function using ripple chain logic does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Implementing a priority function using ripple chain logic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Implementing a priority function using ripple chain logic will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2462688