[SOLVED] concatenation & division problem -Urgent

[shhrikant1]

Hello All,

please see the question below -

There is a 1 bit input say - 'a'
at every raising clock the input concatenated with 'a' again
i.e. at raising clk output will be- 'a' & 'a'
at next rising clk the output will be 'a' & 'a' & 'a'
and so on ...
it means after 10 clock pulse the output will be a 10 bit data which has to be converted to integer & check the divisibility of the number by two.

can any one give me any hint or an algorithm to solve this .
Can we use any gate logic in this algorithm.

Please help its urgent

thanks again

 

[FvM]

We usually call it a shift register. The specification is incomplete, because you don't say if the data is shifted right or left (respectively if the new data is concatenated as MSB or LSB).

 

[shhrikant1]

Thanks FvM for your reply,
The new data is concatenated on left i.e. as MSB
My problem is after every clock pulse the size of the output increases by 1 , how to deal with such a dynamic number ?

 

[allsey87]

You do want a 10 bit shift register, as it asks whether this number is divisible by two, it is reasonably to assume that we are talking about a trivial example involving at 10 bit unsigned number. Now you said it was MSB in first i.e. big endian. give this a try, I haven't simulated or compiled, but this is roughly what you want...

entity Question is
port(a, clock :in std_logic);
end entity Question;

architecture Solution of Question is
signal is_div_2 : std_logic;
signal u10_number : std_logic_vector(9 downto 0);
begin

is_div_2 <= not u10_number(0); -- number is divisible by two if lowest bit is not set

process(clock)
begin
if(rising_edge(clock)) then
for i in 0 to 8 loop
u10_number(i + 1) <= u10_number(i);
end loop;
u10_number(0) <= a;
end if;
end process;

end architecture Solution;

As i said, I haven't simulated or compiled this, but it is roughly what you want. for practical purposes you should add reset and enable logic...

cheers and best of luck, Mike

---------- Post added at 22:59 ---------- Previous post was at 22:53 ----------

** you can't deal with dynamic numbers in hardware. you have a fixed number of flip flops and wires which can be used / interpreted as a number. The only way to solve this dynamically would be using blockRAM and a quite advance state machine to implement a linked list sort of solution. but even this has its upper limits (i.e. the total amount of available blockRAM).

Ultimately all data isn't infinite in any sort of electronic device, e.g. if you keep adding 1 to an int in C eventually it will overflow and wrap round to 0.

 

[shhrikant1]

Hi Mike,

Thanks for your reply I checked your code - it works fine, but my problem is not just to check the divisibility by two ,
I need to concatenate the input with the previous input i.e.
at raising_edge(clk)
a & a(n-1);
at next raising it should be a(n+1) & a & a(n-1) and so on....

after every raising edge of the clock the divisor is increase by 1 bit. as the dividend is constant which is 2.
I need to show the divisor as well along with the result(which can be calculated by your algorithm)
thanks in advance.

 

[TrickyDicky]

does that mean that with each clock , the divider becomes 2^n?
If you mean the divider becomes 2/3/4/5 etc, then you're going to struggle to get this done (dividing by anything other than 2^n is pretty hard).

If it is just 2^n, just check the least significant N bits to see if they are equal to zero (nor them).

 

[FvM]

check the divisibility of the number by two

Nothing is said about 2^n. Divisibility by two is a trivial problem in this case.

 

[shhrikant1]

Thanks for replies, let me correct my statement .. :

I need to concatenate the input with the previous input i.e.
at raising_edge(clk)
a & a(n-1);
at next raising it should be a(n+1) & a & a(n-1) and so on....

after every raising edge of the clock the divisor is increase by 1 bit. as the DIVISOR is constant which is 2.
I need to show the divident as well along with the result(which can be calculated by your algorithm)
thanks in advance.

 

[allsey87]

the divisor is increase by 1 bit. as the DIVISOR is constant which is 2.
I need to show the divident as well along with the result(which can be calculated by your algorithm)
thanks in advance.

How can the divisor increase by 1 bit and be constant...?

This is getting a bit confusing, draw a diagram in paint brush or something and post it to the forum to show us exactly what you mean.

 

[shhrikant1]

Accept my apologies for that typo - I meant to say the dividend is increasing by 1 bit at every clock cycle where as the divisor is a constant - 2
Ex- say the dividend is 8 (3 bit) divisor is 2 i.e 8/2
next clock cycle it will be 15/2
next clock cycle it will be 31/2
next clock cycle it will be 63/2
next clock cycle it will be 127/2 and so on...

How can the divisor increase by 1 bit and be constant...?

This is getting a bit confusing, draw a diagram in paint brush or something and post it to the forum to show us exactly what you mean.

 

[TrickyDicky]

just add an output that is your shift register:

port (
....
dividend : out std_logic_vector(9 downto 0);
..


dividend <= u10_number;

 

[shhrikant1]

Thanks tricky for your reply,

Your suggestion is right but again (9 downto 0) gives me the dividend after 10th raising clock - I mentioned 10 as an example - the concatenation process has to be continued for a long time say 10000 clock or even more ..

just add an output that is your shift register:

port (
....
dividend : out std_logic_vector(9 downto 0);
..


dividend <= u10_number;

 

[TrickyDicky]

that is a lot of bits to show. In code, you can quite easily change it to:

dividend : out std_logic_vector(9999 downto 0);

Or you could just keep the 10 bit window and have an output counter saying how many clocks have elapsed.
The first suggestion will not be possible if you are taking the output off chip (the most expensive FPGAs only have about 1000 IOs). Its also not what you really want to do for internal.

Why would you want to store such a large dividend anyway? each bit added to the bottom does the same as multiplying the previous value by 2.

 

[shhrikant1]

Well its very obvious that (9999 downto 0) is not feasible by any means..
I dont want to implement this design - this is a question asked by a well known company in an interview

 

[TrickyDicky]

without an expansion on the scope or specification it is difficult to give an answer.

If you are just diving the last 10 clocks worth of data by 2, then you only ever need a 10 bit shift register.
If you get stupidly long with the shift reg, you need to start storing the data in a memory.
If you just need to know how many clock cycles have elapsed, you need a counter.

Without knowing the real application, it is difficult to say which of these 3 is appropriate. And, at the end of the day, none of them may be correct.