Priority encoder

 
 
Verified

Priority encoder is a circuit that converts multiple binary inputs into binary representation of the index of active input bit with the highest priority. Each of input has assigned priority. The least significant bit has the highest priority and the most significant bit the lowest. If more than one input is active at the same time the input having highest priority will take precedence. The priority encoder component has an additional output indicating that output signal is valid when at least one input is active. Priority encoders are often used when multiple components are to share common resource or in interrupt controllers. Using a parallel prefix computation (PPC) speeds up calculation and improves the circuit timing.

Truth table

The below table shows the truth table of simple 4bit encoder, ' x' means 'don't care' value.

I(3)

I(2)

I(1)

I(0)

OUT

VALID

0

0

0

0

0 0

0

x

x

x

1

0 0

1

x

x

1

0

0 1

1

x

1

0

0

1 0

1

1

0

0

0

1 1

1

Features

  • Parametrized priority encoding capable of both small and large (up to 8k) input width.
  • Valid output indicating the output is valid.
  • Large encoders built as a structure of smaller encoders.
  • Simple or fast parallel implementation using parallel prefix computation.
  • Optional pipeline registers on the output of each stage of hierarchy.
  • Small building block width selected independently from total input width controlling the number of hierarchy stages and latency of pipeline versions.
  • Clock enable inputs for pipeline stages.

Additional features

  • Synchronous or Asynchronous reset.

Deliverables

  • Verified RTL code
  • Access to detailed design documentation
  • 1 year support and customization service.

Parameters table

Parameter

Valid values

description

TSIZE

2 … 8192

Input width

OSIZE

ceil(log2(TSIZE))

Output width

BSIZE

2 … 8192

(must be power of 2 or equal to TSIZE )

Width of base building block for hierarchical implementations

BTYPE

0,1

Type of base block implementation:
0 – simple implementation

1 – parallel prefix computation

REGS

0,1

Insert registers on output of each hierarchy stage

0 – no registers, combinatorial circuit

1 – registers on output of each layer o basic blocks

Interface table

Signal name

Direction/width

description

clock

Input

Clock signal

resetb

Input

Active low reset signal.

enable

input

Active high clock enable.

request

Input [TSIZE–1:0]

Request input vector

grant

Output [OSIZE–1:0]

Output binary encoded index of the highest priority request bit.

valid

Output

 

Indication that the current grant is valid and is a result of a valid request.

Priority encoding

Priority encoder is a circuit that converts multiple binary inputs into a binary representation of the index of active input bit with the highest priority. Each of input has assigned priority where the least significant bit has the highest priority and the most significant bit the lowest. If more than one input is active at the same time the input having highest priority will take precedence. Additional output signal indicates that output grant is valid.

Hierarchical priority encoding

Encoders for large input widths are implemented as a structure of smaller encoders and additional multiplexers. Inputs of first layer are connected to encoder inputs. Valid outputs of first layer are inputs of second layer and grant outputs of first layer are passed to output of second layer through multiplexers. Using parallel prefix computation algorithm enables faster logic and improves timing performance of circuit.

Parallel prefix computation (PPC)

Parallel prefix computation is a type of parallel calculation serving to reduce the number of stages it takes to calculate a function on multiple inputs by using parallel computations where possible.

The example below is for an OR computation. The main feature of the OR PPC is to transform any vector into a thermometer decoded vector where all bits, starting from the first bit set are set.

The below drawing illustrates the PPC OR computation 

PPC parallel prefix computation

The function of an OR PPC is demonstrated in the following table:
 

Request vector

PPC output

0001

1111

0010

1110

1100

1100

0100

1100

1000

1000

0011

1111

1001

1111

1110

1110

 

PPC based priority encoder

The usage of the PPC computation for a priority encoder results in a thermometer code of the highest priority active input bit the conversion of the result into binary is done by simple encoding.

Pipeline priority encoder

The integration of a priority encoder into a pipeline design is useful in many applications and requires the ability to stall the encoder if the downstream logic is unable to handle the resulting grant. This feature is accomplished by using of clock enable for all encoder's registers. The latency of pipelined priority encoder is determined as ceil( log ( BSIZE, TSIZE ) ).

Valid signal function

The purpose of the valid signal is to enable downstream logic to distinguish between the case where no requests are asserted and the case where request 0 is asserted. Those two cases would result in a binary decoded output of 0 and the valid bit would indicate that request 0 is granted.

 

Test Items

The below table summarizes the test items that were checked for the priority encoder.

Item name

Description

No request.

Check if valid signal is 0 when none of input bits is active.

Single request

Assert each request separately, check for valid grant.

Multiple requests.

Assert random requests and check correctness of valid and grant outputs.

 

Additional test items for the pipelined versions

Item name

Description

Reset functionality

Check if all pipeline stages are set to 0 while reset is active

Stalling encoder by de-asserting enable input

While random assertion and de-assertion of clock enable check if device would stall and further continue previously stalled operation.

Pipeline latency

Check if latency of pipelined versions is always equal to ceil( log ( BSIZE, TSIZE ) )

 

Each of above test items was checked for following configurations of priority encoder:

  1. various widths of simple implementation with BSIZE = TSIZE (simple basic encoder)
  2. various widths of simple implementation with BSIZE = TSIZE (simple basic encoder) with registers on outputs
  3. various widths of PPC implementation with BSIZE = TSIZE (PPC basic encoder)
  4. various widths of PPC implementation with BSIZE = TSIZE (PPC basic encoder) with registers on outputs
  5. various widths of hierarchical implementation with BSIZE < TSIZE based on simple basic encoders
  6. various widths of hierarchical implementation with BSIZE < TSIZE based on PPC basic encoders
  7. various widths of pipelined hierarchical implementation with BSIZE < TSIZE based on simple encoders
  8. various widths of pipelined hierarchical implementation with BSIZE < TSIZE based on PPC encoders

Assumptions

The following assumptions and rules should be followed and can be used as error indications:

1.    BSIZE must be power of 2, except cases when BSIZE is equal TSIZE

2.    OSIZE must be equal ceil(log2(TSIZE))

 

Usability

Priority encoder is designed to be used in the context of decision blocks where all requestors have different priorities the advantages of priority encoder are:

  1. Arbitration, granting requestors depending on their priorities.
  2. Simple integration into pipelined systems.
  3. Fast PPC selection logic.