From Newsgroup: comp.arch

Prompted by my very-probably-never-to-be-built 3n+1 project,
I've looked at the Wikipedia article on digital comparators, https://en.wikipedia.org/wiki/Digital_comparator , and it seems
somewhat strange.

It would seem obvious that an n-bit (unsigned) comparator would
be built from comparisions of individual bits, probably using
"less or equal" and "geater or equal" signals "less or equal"
signals according to

le = (b) | (!a);
ge = (a) | (!b);

which can be turned into two NAND gates with one inverted input
using De Morgan's laws.

The next level would combine two of the previous results with

gt = (!le0 & ge1) | (!le1);
lt = (!ge0 & le1) | (!ge1);

which equivalent to an OAI with one inverted input:

gt = !((le0 | !ge1) & le1);
lt = !((ge0 | !le1) & ge1);

The next level then would use AOI and an inverter to go from gt to
le again. This only takes eight transistors in CMOS for each gt
and lt and should be rather fast.

If anybody wants to look at this, I have uploaded an illustration at https://commons.wikimedia.org/wiki/File:4_bit_digial_comparator.svg

I think that this should be rather fast and should use little
area (eight transistors per OAI+Inverter or AOI+Inverter), but
I absolutely refuse to believe that I am the first person to come
up with this.

I rather suspect that people have been doing this ever since
AOI logic became advantageous (since the days of TTL, at least),
it just hasn't made it into textbooks because comparator receive
little attention compared to adders (pun intended).

Berkeley ABC arrived at the two-bit compartor using NAND and OAI
given just the truth tables (which where I got the idea in from
in the first place).

However, if I put this into the Wikipedia article, this would
count as "original research" and be rejected unless I can cite
a source.

So... does anybody know a source? Or are other schemes possible,
which are even better, and what are these? I do not think that
the implementation in Wikipedia makes sense.
--
This USENET posting was made without artificial intelligence,
artificial impertinence, artificial arrogance, artificial stupidity,
artificial flavorings or artificial colorants.
--- Synchronet 3.21d-Linux NewsLink 1.2

From Newsgroup: comp.arch

Thomas Koenig wrote:

Prompted by my very-probably-never-to-be-built 3n+1 project,
I've looked at the Wikipedia article on digital comparators, https://en.wikipedia.org/wiki/Digital_comparator , and it seems
somewhat strange.

It would seem obvious that an n-bit (unsigned) comparator would
be built from comparisions of individual bits, probably using
"less or equal" and "geater or equal" signals "less or equal"
signals according to

le = (b) | (!a);
ge = (a) | (!b);

which can be turned into two NAND gates with one inverted input
using De Morgan's laws.

The next level would combine two of the previous results with

gt = (!le0 & ge1) | (!le1);
lt = (!ge0 & le1) | (!ge1);

which equivalent to an OAI with one inverted input:

gt = !((le0 | !ge1) & le1);
lt = !((ge0 | !le1) & ge1);

The next level then would use AOI and an inverter to go from gt to
le again. This only takes eight transistors in CMOS for each gt
and lt and should be rather fast.

If anybody wants to look at this, I have uploaded an illustration at https://commons.wikimedia.org/wiki/File:4_bit_digial_comparator.svg

I think that this should be rather fast and should use little
area (eight transistors per OAI+Inverter or AOI+Inverter), but
I absolutely refuse to believe that I am the first person to come
up with this.

I rather suspect that people have been doing this ever since
AOI logic became advantageous (since the days of TTL, at least),
it just hasn't made it into textbooks because comparator receive
little attention compared to adders (pun intended).

Berkeley ABC arrived at the two-bit compartor using NAND and OAI
given just the truth tables (which where I got the idea in from
in the first place).

However, if I put this into the Wikipedia article, this would
count as "original research" and be rejected unless I can cite
a source.

So... does anybody know a source? Or are other schemes possible,
which are even better, and what are these? I do not think that
the implementation in Wikipedia makes sense.

I have a paper but it is just a starting point as people have been
doing unsigned integer comparators forever, as the technologies change.
(You can probably find papers from the 50's on the best way to do
this with triodes or something.)

The basic idea is:
1) xor the A and B inputs to detect where the difference starts
2) do a high-to-low priority selector (find last one) across the
difference bits to get a 1-hot bit where they are first different
3) AND the difference start bit with the input bits gives a 1 where higher

It mostly comes down to building an optimal priority selector,
which in static CMOS should log4 gate delays.

This is just a paper I happen to have:

High-Performance and Power-Efficient CMOS Comparators 2003 https://www.researchgate.net/profile/Jinn-Shyan-Wang-2/publication/2982173_High-performance_and_power-efficient_CMOS_comparators/links/0fcfd50e780845a1c0000000/High-performance-and-power-efficient-CMOS-comparators.pdf

The below list of related articles is quite long:

https://scholar.google.com/scholar?q=related:N6b1f6pKJtMJ:scholar.google.com/&scioq=%22High-Performance+and+Power-Efficient+CMOS+Comparators%22&hl=en&as_sdt=0,5

This is all for ASIC, none of this applies to FPGA's.
For FPGA's the fastest is likely to do a subtract and check for a
borrow out as they have optimized the carry chains.


--- Synchronet 3.21d-Linux NewsLink 1.2

From Newsgroup: comp.arch

EricP <ThatWouldBeTelling@thevillage.com> schrieb:

I have a paper but it is just a starting point as people have been
doing unsigned integer comparators forever, as the technologies change.
(You can probably find papers from the 50's on the best way to do
this with triodes or something.)

The basic idea is:
1) xor the A and B inputs to detect where the difference starts
2) do a high-to-low priority selector (find last one) across the
difference bits to get a 1-hot bit where they are first different
3) AND the difference start bit with the input bits gives a 1 where higher

It mostly comes down to building an optimal priority selector,
which in static CMOS should log4 gate delays.

A single gate delay for count trailing zeros of four bits? OK,
that sounds fast.

I guess that that is faster than what I dreamed up, which
is no big surprise :-)

This is just a paper I happen to have:

High-Performance and Power-Efficient CMOS Comparators 2003 https://www.researchgate.net/profile/Jinn-Shyan-Wang-2/publication/2982173_High-performance_and_power-efficient_CMOS_comparators/links/0fcfd50e780845a1c0000000/High-performance-and-power-efficient-CMOS-comparators.pdf

The below list of related articles is quite long:

https://scholar.google.com/scholar?q=related:N6b1f6pKJtMJ:scholar.google.com/&scioq=%22High-Performance+and+Power-Efficient+CMOS+Comparators%22&hl=en&as_sdt=0,5

That sounds interesting. The problem is that everybody is doing things
that are faster than anybode else. If one adds all the claims,
the results should be arriving half an hour before the data :-)

(Similar for patent literature, truth be told).

This is all for ASIC, none of this applies to FPGA's.
For FPGA's the fastest is likely to do a subtract and check for a
borrow out as they have optimized the carry chains.

Sounds reasonable.
--
This USENET posting was made without artificial intelligence,
artificial impertinence, artificial arrogance, artificial stupidity,
artificial flavorings or artificial colorants.
--- Synchronet 3.21d-Linux NewsLink 1.2

From Newsgroup: comp.arch

Thomas Koenig wrote:

EricP <ThatWouldBeTelling@thevillage.com> schrieb:

I have a paper but it is just a starting point as people have been
doing unsigned integer comparators forever, as the technologies change.
(You can probably find papers from the 50's on the best way to do
this with triodes or something.)

The basic idea is:
1) xor the A and B inputs to detect where the difference starts
2) do a high-to-low priority selector (find last one) across the
difference bits to get a 1-hot bit where they are first different
3) AND the difference start bit with the input bits gives a 1 where higher >>
It mostly comes down to building an optimal priority selector,
which in static CMOS should log4 gate delays.

A single gate delay for count trailing zeros of four bits? OK,
that sounds fast.

I guess that that is faster than what I dreamed up, which
is no big surprise :-)

The brute force way is for each output to look just at its
next higher neighbor bit, but that gives a linear delay growth.

O[63] = I[63]
O[62] = I[62] & ~O[63]
...
O[ 1] = I[ 1] & ~O[ 2]
O[ 0] = I[ 0] & ~O[ 1]

gives a delay of 64 gates.

The optimized priority selector is a special case of what is
called a Parallel Prefix Tree or Parallel Prefix Network.

For N inputs it scales O(log4(N)) because max fan-in is 4,
so priority select on a 64 bit vector has 3 levels of look ahead,
16 groups of 4*1 bits, 4 groups of 4*4 bits, 1 group of 4*16 bits.
Plus a layer of AND gates to enable the highest output.
So 4 gate delays.

--- Synchronet 3.21d-Linux NewsLink 1.2

From Newsgroup: comp.arch


EricP <ThatWouldBeTelling@thevillage.com> posted:

Thomas Koenig wrote:

Prompted by my very-probably-never-to-be-built 3n+1 project,
I've looked at the Wikipedia article on digital comparators, https://en.wikipedia.org/wiki/Digital_comparator , and it seems
somewhat strange.

It would seem obvious that an n-bit (unsigned) comparator would
be built from comparisions of individual bits, probably using
"less or equal" and "geater or equal" signals "less or equal"
signals according to

le = (b) | (!a);
ge = (a) | (!b);

which can be turned into two NAND gates with one inverted input
using De Morgan's laws.

The next level would combine two of the previous results with

gt = (!le0 & ge1) | (!le1);
lt = (!ge0 & le1) | (!ge1);

which equivalent to an OAI with one inverted input:

gt = !((le0 | !ge1) & le1);
lt = !((ge0 | !le1) & ge1);

The next level then would use AOI and an inverter to go from gt to
le again. This only takes eight transistors in CMOS for each gt
and lt and should be rather fast.

If anybody wants to look at this, I have uploaded an illustration at https://commons.wikimedia.org/wiki/File:4_bit_digial_comparator.svg

I think that this should be rather fast and should use little
area (eight transistors per OAI+Inverter or AOI+Inverter), but
I absolutely refuse to believe that I am the first person to come
up with this.

I rather suspect that people have been doing this ever since
AOI logic became advantageous (since the days of TTL, at least),
it just hasn't made it into textbooks because comparator receive
little attention compared to adders (pun intended).

Berkeley ABC arrived at the two-bit compartor using NAND and OAI
given just the truth tables (which where I got the idea in from
in the first place).

However, if I put this into the Wikipedia article, this would
count as "original research" and be rejected unless I can cite
a source.

So... does anybody know a source? Or are other schemes possible,
which are even better, and what are these? I do not think that
the implementation in Wikipedia makes sense.

I have a paper but it is just a starting point as people have been
doing unsigned integer comparators forever, as the technologies change.
(You can probably find papers from the 50's on the best way to do
this with triodes or something.)

The basic idea is:
1) xor the A and B inputs to detect where the difference starts
2) do a high-to-low priority selector (find last one) across the
difference bits to get a 1-hot bit where they are first different
3) AND the difference start bit with the input bits gives a 1 where higher

It mostly comes down to building an optimal priority selector,
which in static CMOS should log4 gate delays.

It is closer to log3.5 than log4. The NAND layers in the comparison can
have Fan-In 4 but we generally want the NOR layers to have Fan-In 3 due
to the slower speed of P-channel gates compared to N-channel gates.

This is just a paper I happen to have:

High-Performance and Power-Efficient CMOS Comparators 2003 https://www.researchgate.net/profile/Jinn-Shyan-Wang-2/publication/2982173_High-performance_and_power-efficient_CMOS_comparators/links/0fcfd50e780845a1c0000000/High-performance-and-power-efficient-CMOS-comparators.pdf

The below list of related articles is quite long:

https://scholar.google.com/scholar?q=related:N6b1f6pKJtMJ:scholar.google.com/&scioq=%22High-Performance+and+Power-Efficient+CMOS+Comparators%22&hl=en&as_sdt=0,5

This is all for ASIC, none of this applies to FPGA's.
For FPGA's the fastest is likely to do a subtract and check for a
borrow out as they have optimized the carry chains.

--- Synchronet 3.21d-Linux NewsLink 1.2

From Newsgroup: comp.arch


Thomas Koenig <tkoenig@netcologne.de> posted:

Prompted by my very-probably-never-to-be-built 3n+1 project,
I've looked at the Wikipedia article on digital comparators, https://en.wikipedia.org/wiki/Digital_comparator , and it seems
somewhat strange.

It would seem obvious that an n-bit (unsigned) comparator would
be built from comparisions of individual bits, probably using
"less or equal" and "geater or equal" signals "less or equal"
signals according to

le = (b) | (!a);
ge = (a) | (!b);

which can be turned into two NAND gates with one inverted input
using De Morgan's laws.

The next level would combine two of the previous results with

gt = (!le0 & ge1) | (!le1);
lt = (!ge0 & le1) | (!ge1);

which equivalent to an OAI with one inverted input:

gt = !((le0 | !ge1) & le1);
lt = !((ge0 | !le1) & ge1);

The next level then would use AOI and an inverter to go from gt to
le again. This only takes eight transistors in CMOS for each gt
and lt and should be rather fast.

You should consider a comparitor (signed or unsigned) to be an XOR
gate followed by a "carry chain" which has been "tree-ified".

If anybody wants to look at this, I have uploaded an illustration at https://commons.wikimedia.org/wiki/File:4_bit_digial_comparator.svg

I think that this should be rather fast and should use little
area (eight transistors per OAI+Inverter or AOI+Inverter), but
I absolutely refuse to believe that I am the first person to come
up with this.

I rather suspect that people have been doing this ever since
AOI logic became advantageous (since the days of TTL, at least),
it just hasn't made it into textbooks because comparator receive
little attention compared to adders (pun intended).

Berkeley ABC arrived at the two-bit compartor using NAND and OAI
given just the truth tables (which where I got the idea in from
in the first place).

However, if I put this into the Wikipedia article, this would
count as "original research" and be rejected unless I can cite
a source.

So... does anybody know a source? Or are other schemes possible,
which are even better, and what are these? I do not think that
the implementation in Wikipedia makes sense.

--- Synchronet 3.21d-Linux NewsLink 1.2