Sorting numbers in hardware

Patent metadata

Field	Value
Publication number	US-10175943-B2
Application number	US-201715497373-A
Country	US
Kind code	B2
Filing date	Apr 26, 2017
Priority date	Apr 26, 2016
Publication date	Jan 8, 2019
Grant date	Jan 8, 2019

Abstract

An efficient hardware apparatus for calculating the maximum and/or minimum of two n-bit binary input values generates a number of separate select signals, each of which is then used to control the selection of a single bit from one of the two binary inputs. A select signal for an i th bit of the output depends upon bits [n−1, i] in each of the two binary inputs and based on the select signal the i th bit is selected from one of the two inputs.

First claim

The invention claimed is:

1. A hardware arrangement arranged to receive first and second n-bit input values and output an n-bit maximum value and/or an n-bit minimum value selected from the two input values, the hardware arrangement comprising:
n first logic blocks, wherein an i th first logic block is arranged to receive an i th bit from each of the input values and output an initial signal indicating whether the i th bit from the first input value is greater than the i th bit from the second input value;
n or n−1 second logic blocks, wherein an i th second logic block is arranged to receive an i th bit from each of the input values and output an initial signal indicating whether the i th bit from the first input value is equal to the i th bit from the second input value;
a plurality of third logic blocks arranged to receive a plurality of signals from one or more of a first logic block, second logic block, and another third logic block, the signals comprising a signal indicating whether a group of one or more bits from the first input value are greater than a corresponding group of bits from the second input value, a signal indicating whether the group of bits from the first input value are equal to the corresponding group of bits from the second input value and a signal indicating whether an adjacent group of one or more bits from the first input value are greater than the corresponding adjacent group of bits from the second input value and to combine the received signals using logic gates to output an intermediate signal indicating whether a larger group of bits from the first input value are greater than a corresponding larger group of bits from the second input value, the larger group of bits comprising the group of one or more bits and the adjacent group of one or more bits;
a plurality of fourth logic blocks arranged to receive a signal indicating whether a group of one or more bits from the first input value are equal to a corresponding group of bits from the second input value and a signal indicating whether an adjacent group of one or more bits from the first input value are equal to a corresponding adjacent group of bits from the second input value and to combine the received signal using a logic gate to output an intermediate signal indicating whether a larger group of bits from the first input value are equal to a corresponding larger group of bits from the second input value, the larger group of bits comprising the group of one or more bits and the adjacent group of one or more bits; and
wherein the plurality of third logic blocks are arranged in two or more hardware stages, wherein a first hardware stage generates intermediate signals for pairs of adjacent bits and a second hardware stage generates intermediate signals for tuples and quads of adjacent bits; and
wherein the hardware arrangement further comprises n−1 fifth logic blocks, wherein a fifth logic block is arranged to receive a signal output from a third logic block and based on the received signal to output a bit from either the first input value or the second input value such that an i th bit of the output value is selected based on a comparison of bits [n−1, i] from each of the input values, wherein n−1≥i≥0.

2. The hardware arrangement according to claim 1 , wherein an i th first logic block comprises:
a first input arranged to receive the i th bit from the first input value;
a second input arranged to receive the i th bit from the second input value;
a NOT gate having an input connected to the second input; and
an AND gate having an input connected to the first input, an input connected to an output of the NOT gate and an output arranged to output the initial signal indicating whether the i th bit from the first input value is greater than the i th bit from the second input value.

3. The hardware arrangement according to claim 1 , wherein an i th second logic block comprises:
a first input arranged to receive the i th bit from the first input value;
a second input arranged to receive the i th bit from the second input value;
a NOT gate having an input connected to the second input; and
an XOR gate having an input connected to the first input, an input connected to an output of the NOT gate and an output arranged to output the initial signal indicating whether the i th bit from the first input value is equal to the i th bit from the second input value.

4. The hardware arrangement according to claim 1 , wherein an i th second logic block comprises:
a first input arranged to receive the i th bit from the first input value;
a second input arranged to receive the i th bit from the second input value;
a NOT gate having an input connected to the second input; and
an OR gate having an input connected to the first input, an input connected to an output of the NOT gate and an output arranged to output the initial signal indicating whether the i th bit from the first input value is equal to the i th bit from the second input value.

5. The hardware arrangement according to claim 1 , wherein a third logic block comprises:
a first input arranged to receive a signal indicating whether a group of bits from the first input value are greater than a corresponding group of bits from the second input value;
a second input arranged to receive a signal indicating whether the group of bits from the first input value are equal to the corresponding group of bits from the second input value;
a third input arranged to receive a signal indicating whether an adjacent group of bits from the first input value are greater than the corresponding adjacent group of bits from the second input value;
an AND gate having an input connected to the second input and an input connected to the third input; and
an OR gate having an input connected to the first input, an input connected to an output of the AND gate and an output arranged to output an intermediate signal indicating whether a larger group of bits from the first input value are greater than a corresponding larger group of bits from the second input value, the larger group of bits comprising the group of bits and the adjacent group of bits.

6. The hardware arrangement according to claim 1 , wherein a fourth logic block comprises:
a first input arranged to receive a signal indicating whether a group of bits from the first input value are equal to a corresponding group of bits from the second input value;
a second input arranged to receive a signal indicating whether an adjacent group of bits from the first input value are equal to a corresponding adjacent group of bits from the second input value; and
an AND gate having an input connected to the first input, an input connected to the second input and an output arranged to output an intermediate signal indicating whether a larger group of bits from the first input value are equal to a corresponding larger group of bits from the second input value, the larger group of bits comprising the group of bits and the adjacent group of bits.

7. A hardware arrangement according to claim 1 , wherein an m th hardware signal generates intermediate signals for groups of 2 m , 2 m −1, 2 m −2, . . . , 2 m-1 +1 adjacent bits.

8. The hardware arrangement according to claim 1 , wherein the plurality of third logic blocks are arranged in h hardware stages, wherein 2 h ≥n>2 h-1 , 1≤m≤h and an m th hardware stage comprises T third logic blocks, where

T
≤

⌊

n

2
m

Assignees

• Imagination Tech Ltd

Inventors

• Drane Theo Alan
• Rose Thomas Michael

Classifications

• G06F7/24 Primary

  Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers {sorting methods in general}(G06F7/36 takes precedence) · CPC title

• H03K19/17724

  Structural details of logic blocks · CPC title

• H03K19/21

  EXCLUSIVE-OR circuits, i.e. giving output if input signal exists at only one input; COINCIDENCE circuits, i.e. giving output only if all input signals are identical · CPC title

• G06F7/26 Primary

  the sorted data being recorded on the original record carrier within the same space in which the data had been recorded prior to their sorting, without using intermediate storage · CPC title

• G06F7/026 Primary

  Magnitude comparison, i.e. determining the relative order of operands based on their numerical value, e.g. window comparator · CPC title