digital design problem

As a part of a larger project I'm currently designing a small module that will take 13 bits as an input and will output the commonest value in the input at its output. Ie: it will output a 1 if there are 7 or more bits set in the input, and will output a 0 otherwise. The design is beeing done in VHDL.

My first attempt was to write a process with for loop that counted the number of bits set in a variable and then setted the output bit accordingly. The problem with this approach was that the synthesizer inferred 12 4-bit adders and so the design was way too big and way too slow.

After some other failed attempts I stumbled upon this solution:

library IEEE; use IEEE.std_logic_1164.all;

entity bit_decide is port ( Bits_in : in std_logic_vector (12 downto 0); Bit_out : out std_logic ); end entity bit_decide;

architecture bit_decide_arc of bit_decide is

type partcnt_t is array (3 downto 0) of integer range 0 to 3; type partcnt2_t is array (1 downto 0) of integer range 0 to 6;

signal partial_count : partcnt_t; signal partial_count2 : partcnt2_t; signal bits_set_count : integer range 0 to 13;

begin

with Bits_in (2 downto 0) select partial_count(0)

Reply to
Antonio
Loading thread data ...

The quickest solution isn't digital.

Hook up each of the 13 binary outputs to a resistor - let's say 1k part

- and tie the free ends of the resistors together.

Assuming 5V power supplies and CMOS drivers, with 7 high inputs and six low, the common point with be at 2.692V wrt to the 0V rail. With 6 inputs high and 7 low, this falls to 2.308V.

Tie this common point to one input of a comparator, tie the other input to a 1:1 divider between the power rails, and you've got a system that will react as fast as your comparator - the LT1016 offers 9nsec typical and 15nsec worst case

formatting link

Despite the description, this doesn't really qualify as an "ultrafast comparator" these days - there are ECL parts around that a ten times faster. It is one of the better behaved comparators, and digital engineers have been known to use them without provoking them into oscillation (but read the whole data sheet).

--
Bill Sloman, Nijmegen
Reply to
bill.sloman

You do seem to be going about it the hard way You can either figure out the required minterms (how many combinations of 7 bits are there in 13 bits?), make AND functions and OR them together

... reg data[12:0]; wire vote; assign vote = (data[12] & data[11] & data[10] & data[9] & data[8] & data[7] & data[6]) | (data[12] & data[10] & data[9] & data[8] & data[7] & data[6] & data[5]) | ....

etc OR just use a shift register

module majorityvote(indata, out, clk, start); input [12:0] indata; // the 13 bits, latched somewhere external to this module output out; // the result input clk; // to clock things around input start; // take high to run the sequence, assumed to be externally synchronised. Take low before 13 clocks. reg [3:0] bitcount; reg [3:0] count; assign out = (count > 3'b110) ? 1 : 0;

always @(posedge clk) begin if(!start) begin count

Reply to
PeteS

A quick note about the minterm solution:

Although there are thousands of possibilities of 7 or more bits set, you don't care about the 'more' - if there are any 7 bits set, that's all you care about. The speed will be dictated by the propagation delays and the levels of logic needed to implement the terms. A good compiler (with lots of resources) will do that in 2 levels of logic at a minimum (1 for each and term, assuming they are all paralleled) and one for the OR term (assuming it can parallel the 7 bits - this is the one it probably can't parallel).

Cheers

PeteS

Reply to
PeteS

Thanks for the suggestion. I really think that this should work OK. I didn't thought of performing the computation on the fly. *blushes*

Your solution is what I needed, as the data actually comes in a serial interface. I suppose I became too single minded about doing it in a single cycle.

I needed the computation to be done in 20 ns which is the clock period of the design. My previous attemps all incurred in a delay in the range of 23 ~ 35 ns.

Thanks again. And Happy New Year!

Reply to
Antonio

--
Snipped design description.
Reply to
John Fields

You're probably forcing the compiler into doing some unnecessary partial results that it could otherwise optimize out. I think the first part is fine. I played around with the end part and reduced the slices from 15 to 10, LUTs from 27 to 18, levels of logic from 12 to 7 and static delay estimate from 27ns to 17ns. This is what I did:

signal threshold: integer range 5 to 6; ... with Bits_in(12) select threshold

Reply to
Spehro Pefhany

Sure, but there's still 1716 minterms if my quickie C program was correct.

Best regards, Spehro Pefhany

--
"it\'s the network..."                          "The Journey is the reward"
speff@interlog.com             Info for manufacturers: http://www.trexon.com
Embedded software/hardware/analog  Info for designers:  http://www.speff.com
Reply to
Spehro Pefhany

Or just use the combinatorial formula,

Pick m objects out of a set of n--

n!/((n-m)!*m!) = 13!/(7!*6!) = 1716

Best regards, Spehro Pefhany

--
"it\'s the network..."                          "The Journey is the reward"
speff@interlog.com             Info for manufacturers: http://www.trexon.com
Embedded software/hardware/analog  Info for designers:  http://www.speff.com
Reply to
Spehro Pefhany

How fast/cheap can an 8K x 8 ROM (e.g., 2764-type) be had? Use all 13 bits as address, and output a high when 7 or more of the input bits are high, and so on. 8K x 1 would work - or a 1K x 8 and a 1 of 8 data selector...

Or is that what you guys are saying? ;-) (I'd have done it in schematic.)

Cheers! Rich

Reply to
Rich Grise

10 slices doesn't cost much if you've got the FPGA anyhow, and I don't think 20ns is in the cards for a 2764.

We're operating a level of abstraction above the schematic.

formatting link

But if he can do it serially, it becomes MUCH less complex.

Best regards, Spehro Pefhany

--
"it\'s the network..."                          "The Journey is the reward"
speff@interlog.com             Info for manufacturers: http://www.trexon.com
Embedded software/hardware/analog  Info for designers:  http://www.speff.com
Reply to
Spehro Pefhany

--
My pleasure; glad I could help. :-)

Happy New Year to you too.
Reply to
John Fields

Why not add the bits together into a four bit number, add two, and take the MSB as the over/under?. Using the Xilinx carry chains can make the addition quite fast.

--
  Keith
Reply to
Keith

Table lookup, of course.

--
Many thanks,

Don Lancaster                          voice phone: (928)428-4073
Synergetics   3860 West First Street   Box 809 Thatcher, AZ 85552
rss: http://www.tinaja.com/whtnu.xml   email: don@tinaja.com

Please visit my GURU\'s LAIR web site at http://www.tinaja.com
Reply to
Don Lancaster

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.