Continue to Site

Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronics Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

Register Log in

Detecting a pattern in a parallel bus random start bit

Status
Not open for further replies.
T

troy99xx

Newbie level 6
Joined
Jul 24, 2012
Messages
13
Helped
0
Reputation
0
Reaction score
0
Trophy points
1,281
Activity points
1,486
I have a parallel bus of 32 bits changing value on every clock cycle @ 50 mhz
I need to detect pattern 0111111111111111111111111111111 [31..0] (bit 31 is a zero)
The pattern can start at any bit position of the parallel bus
This mean that I can get the 'zero bit" on i.e bit 19 of the parallel bus and I will have to look at the previous word to get the full 31 bits of '1"

example
.....Bus . 31..0
clk_0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
clk_1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
clk_2 ...

The pattern is in bold.
After the pattern is detected, I am immediately required to look for another pattern on bit 20 of clk_1

I was thinking about a shift register but I can't serialize fast enough to look for pattern and keep the old data...

Can someone help with some pointers of how I can do this


I will have fifo to go from the 49 Mhz clock domain to a 133MHZ clock

thank you
 

You may have to build an array of diodes and resistors. Some go to ground. Some go to supply +. All join to a single output. It is a typical method to detect a unique combination of 1's and 0's.

The output will change state only when your unique pattern occurs. The change will be immediate.
 

A good starting point will be the 'log2' function [1] since log2(x) will be the index of the most significant bit of 'x' when represented as a binary number. In your case if the input is a std_logic_vector, then you will do something like this...

Code: 
signal x:  std_logic_vector(31 downto 0);
signal Log2_x: natural range x'range;
if (x(31) = '1') then
    Log2_x <= 31; -- The 'to_integer' function can sometimes be unhappy if you try to feed it a full 32 bit number.
else
    Log2_x <= log2(to_integer(unsigned(x)));
end if;

Now that you know the index of the most significant bit that contains a 1, you should be able to make some additional progress on your own. If not, ask some additional pointed questions.

Kevin Jennings

[1] Synthesizable log2 function can be located here in section 4.1 http://www.eda.org/comp.lang.vhdl/FAQ1.html
 

Realistically, I would start with 32 comparators of 32b. Exactly one, or zero of the bits will be set.

From here you have your choice of combined encoder+mux implementation. There are several choices here, but the straightforward encoder+mux seems reasonable. (this is also the Log2_x function above)

Finally, you have a 32b comparator to see if any of the inputs matched. (and any registers/logic to record lock, lock-changed, etc...)

50MHz is likely slow enough that no pipelining will be required, although each of these steps can be pipelined if needed/desired.

(The referenced article only claims the Log2_f function synthesizes for compile time constants, although it may work one at least some synthesizers)
 

troy99xx said:
This mean that I can get the 'zero bit" on i.e bit 19 of the parallel bus and I will have to look at the previous word to get the full 31 bits of '1"
Click to expand...

I realize this means my suggestion in post #2 will not work. My method requires that all inputs be simultaneous.
 

Hi,

I think you need to store the actual value and the previous value.
Imagine as if they were in series giving a 64 bit word.

Then - I don't have a better solution - use 32 independent 32 bit comparators each for the possible match pattern.
"OR" all 32 comparator "equal" outputs to get a single output.

Klaus
 
Ah, I may have misunderstood. In my post #4, the combined encoder-mux assumes you want to align the data with this event for follow-on processing. If you only want to detect it, then the thirty-two 32b compares + 32 input "or" will be enough. This solution is the easiest to understand.

If all that is needed is the detection and no information about the location, there are potentially better solutions that misuse the +/- operators. They are cryptic to read and are only better given certain assumptions about the FPGA architecture. As a result, they are not advisable.
 

Due to the simplicity of the pattern to be detected on which one 0 followed by a sequence of 1´s being streamed, I would expect a simple recursive approach based on a combinational logic, such as the sketch bellow :

circuit.png

Seems like just probing the first and last FF's of the [0-30] array, and also the 31th bit could suffice.
 

vGoodtimes said:
The referenced article only claims the Log2_f function synthesizes for compile time constants, although it may work one at least some synthesizers
Click to expand...
The recursive function version of the referenced code does synthesize for signals, not just for computing constants.

Kevin

- - - Updated - - -

K-J said:
A good starting point will be the 'log2' function
Click to expand...
Actually, I don't think the log2 function will be so useful after all. For whatever reason, I didn't notice that all of the bits in the example that are to the left of the zero are 1, not 0. So all you can do is an exhaustive search of all 32 bits to find the leftmost 0. It's not at all clear what you want to do after that. Are you just trying to detect that you have a zero somewhere, like this...

Code: 
Got_A_Zero <= '0' when (x = x"FFFF_FFFF") else '1';

Or are you trying to find the index of that first zero. The following function will return an index of where a zero was located.

Code: 
signal x: std_logic_vector(31 downto 0);
function Find_First_Zero(L: std_logic_vector) return natural is
begin
   for i in L'range loop
      if (L(i) = '0') then
         return(i);
     end if;
   end loop;
   return(L'right);
end function Find_First_Zero;
...
if Find_First_Zero(x) > 0 then
   -- Do whatever you are supposed to do after finding the zero
elsif (x(0) = '1') then
   -- Do whatever you are supposed to do after finding the zero
else
   -- Do whatever you are supposed to do after not finding the zero
end if;

You would need to save the result of the function for each cycle as well and check that you had an all 1 pattern from the previous input.

Kevin
 

troy99xx said:
I have a parallel bus of 32 bits changing value on every clock cycle @ 50 mhz
I need to detect pattern 0111111111111111111111111111111 [31..0] (bit 31 is a zero)
The pattern can start at any bit position of the parallel bus
This mean that I can get the 'zero bit" on i.e bit 19 of the parallel bus and I will have to look at the previous word to get the full 31 bits of '1"

example
.....Bus . 31..0
clk_0..... 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
clk_1..... 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
clk_2..... 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1

The start pattern is in bold.
After the pattern is detected, I am immediately required to look for another pattern on bit 20 of clk_1

the data msg start byte begins @ bit 31..29 on clk_1
the rest of the byte is @ bits 4..0 on clk_2


So the data msg byte is 7..0 ( bits 7..5 from clk_1 bits 31..29, and bits 4..0 from clk_2 bits 4..0)
The byte value can be be 8 different values that concern my design (it will not be the sync pattern or all 0XFF) .
Click to expand...

I am adding more clarification...

The first pattern 0111111111111111111111111111111 [31..0] is like a sync pattern to start looking for a msg data packet right after. Again, the msg data package can start at any bit of the 32-bit bus input. So for example, as shown above, the start of the data msg can start at any bit of the parallel bus.

The data msg packets come all the time and the sync pattern every so often.

After the detection of the first byte of the data msg, I know how many consecutive bytes are data. Then, I continue scanning for the beginning of another data packet again or a sync packet may come again.

thanks
 
Last edited:

Hi,

a loop with 32 steps each shifiting and comparing needs 32 x 50MHz = 1.6GHz.

I think there is a need for parallel operating.

But maybe the "for...loop" results in parallel operation.

Klaus
 
KlausST said:
Hi,

a loop with 32 steps each shifiting and comparing needs 32 x 50MHz = 1.6GHz.

I think there is a need for parallel operating.

But maybe the "for...loop" results in parallel operation.

Klaus
Click to expand...

Yes, this exactly my problem.. shifting is not an option. Can you expand on the for loop idea? thanks
 

Your description of the data processing problem is still vague.

What's understandable so far:
- You have a word rate of 50 MHz
- You are awaiting a sync pattern formed by by one zero, all other bits 1
- The words succeeding the sync pattern have to be processed according to the '0' position (e.g. shifted by a number of bits that would left align the zero, the point isn't quite clear)

You didn't tell yet:
- Where to send the processed succeeding data or what to do with it?
- There might be a criterion to return to the search sync state you didn't tell.

You would want to define the external design interface, this clarifies about the involved input and output signals.
 

troy99xx said:
Yes, this exactly my problem.. shifting is not an option. Can you expand on the for loop idea? thanks
Click to expand...
As both FvM and I mentioned, it's not clear what you're trying to do other than detecting a sync pattern. Then what? You have new data coming in every clock cycle, but you haven't said how many clock cycles of latency are allowed to do whatever it is that you're trying to do with the rest of the incoming data.

- The 'Find_First_Zero' function I posted in #9 should locate the leftmost zero. From that you now know where the start of the message data packet is located.
- *Presumably*, you want to then grab that first byte of the message and decode it some fashion because you said "After the detection of the first byte of the data msg, I know how many consecutive bytes are data". If that's the case, then that first byte will simply be a right shift of the input data by a dynamic number that is determined by the output of the 'Find_First_Zero' function. The problem here will be that this is a barrel shifter which will be large and slow but maybe it is still fast enough and small enough for your purposes. If not, then you will have to pipeline the shifting operation, but you haven't stated the latency requirements, if any. The tradeoff will be that the lower the latency requirement, the more logic resources will be needed and the slower the clock speed will be. At most, a five clock cycle latency would be needed to shift the input into the proper location for the subsequent logic to then decode and process.
- Now that you have the first byte, all the subsequent bytes will need to be similarly shifted again *presuming* that you're going to be doing something with these bytes of data.

Then there are other considerations such as that first byte might not be located in the same input word. Once you know where the sync pattern ends, you could have anywhere from 0 to 8 bits of that first byte in that 32 bit word. Beyond that, the number of bytes in a particular message is not fixed so then you have to decode the first byte to figure out the length. Once you do have the message decoded, then what do you do with it?

So, you can either try to describe the entire processing flow, or maybe just the area that is actually giving you the problem right now. I'm guessing that your issue right now is
- How to find the location of the end of the sync pattern (Possible solution would be the 'Find_First_Zero' function that I described).
- How to shift the input data the proper number of times in order to be able to decode the message (Solution is a barrel shifter, likely a pipelined barrel shifter but not necessarily).

Kevin
 

K-J said:
The recursive function version of the referenced code does synthesize for signals, not just for computing constants.
Click to expand...
Nice, does it synthesize to an encoder?

Yes, this exactly my problem.. shifting is not an option. Can you expand on the for loop idea? thanks
Click to expand...

I think it would look a lot like my description from post #4.


if this helps:
Code: 
function orReduce(x : std_logic_vector) return std_logic is
  variable result = '0';
begin
  for i in x'range loop
    result := result or x(i);
  end loop;
  return result;
end function;

function createEqualityVector(x : std_logic_vector) return std_logic_vector is
  const kPattern : std_logic_vector(31 downto 0) := x"7FFFFFFF";
  variable xNml : std_logic_vector(x'length-1 downto 0);
  variable result : std_logic_vector(x'length-kPattern'length-1 downto 0) := (others => '0');
begin
  xNml := x;
  for i in result'range loop
    if xNml(kPattern'length-1+i downto i) = kPattern then
      result(i) := '1';
    end if;
  end loop;
  return result;
end function;

function encoder32(x : std_logic_vector) return natural is
  const kMask4 : std_logic_vector(31 downto 0) := x"FFFF0000";
  const kMask3 : std_logic_vector(31 downto 0) := x"FF00FF00";
  const kMask2 : std_logic_vector(31 downto 0) := x"F0F0F0F0";
  const kMask1 : std_logic_vector(31 downto 0) := x"CCCCCCC";  
  const kMask0 : std_logic_vector(31 downto 0) := x"AAAAAAA";
  variable xNml : std_logic_vector(31 downto 0);
  variable resultBits : unsigned(4 downto 0) := (others => '0');
begin
  xNml := x;
  result(4) := orReduce(xNml&kMask4);
  result(3) := orReduce(xNml&kMask3);
  result(2) := orReduce(xNml&kMask2);
  result(1) := orReduce(xNml&kMask1);
  result(0) := orReduce(xNml&kMask0);
  return to_integer(resultBits);
end function;

function barrelShift32(x : std_logic_vector, idx : natural) return std_logic_vector
  variable xNml : std_logic_vector(x'length-1 downto 0);
begin
  xNml := x;
  return x(31+idx downto idx);
end function;

I wrote these in ten minutes before catching a train, so you might want to review them. Some/all of them could be moved out of functions and into the process itself. Some of them are generic, some are not. You should easily be able to combine these to create a working design.
 
Last edited:

As both FvM and I mentioned, it's not clear what you're trying to do other than detecting a sync pattern. Then what? You have new data coming in every clock cycle, but you haven't said how many clock cycles of latency are allowed to do whatever it is that you're trying to do with the rest of the incoming data.

The sync pattern is a guarantee that the next data msg detected is the first byte of that of the data packet. It is to be sure that the device receiving the data is in sync. I will probably reset FSM that process the data msg to start at the beginning knowing that the next data byte is the first byte of the data packet and start counting the number of valid bytes that follow). All this valid bytes with data will be put into a 32-bit word output to another module with a Signal_valid bit.




- The 'Find_First_Zero' function I posted in #9 should locate the leftmost zero. From that you now know where the start of the message data packet is located.

OK


- *Presumably*, you want to then grab that first byte of the message and decode it some fashion because you said "After the detection of the first byte of the data msg, I know how many consecutive bytes are data". If that's the case, then that first byte will simply be a right shift of the input data by a dynamic number that is determined by the output of the 'Find_First_Zero' function. The problem here will be that this is a barrel shifter which will be large and slow but maybe it is still fast enough and small enough for your purposes. If not, then you will have to pipeline the shifting operation, but you haven't stated the latency requirements, if any. The tradeoff will be that the lower the latency requirement, the more logic resources will be needed and the slower the clock speed will be. At most, a five clock cycle latency would be needed to shift the input into the proper location for the subsequent logic to then decode and process.

After the sync pattern, it could be the next clock or 1000’s of clocks before the first byte of a data packet appears on the bus ( the interface will keep sending all 0xFF meanwhile).
This byte will have 8 (types) unique values that are specific for me to detect. Every one of those msg types and bytes that follow need to be sent to another block that will decompress the information to extract the usable data. Just to be clear each data type will correlate to a different module sending x number of bytes.

The data stream can come this way:
Type1_byte_first | Type2_byte_first| Type1_byte_second| Type3_byte_first| Type2_byte_second… etc (intermixed)
Each byte encodes the data type for me to keep count of the number bytes for each source.
This sequence could be on every clock cycle or 100’s of clocks apart between bytes of any type

- Now that you have the first byte, all the subsequent bytes will need to be similarly shifted again *presuming* that you're going to be doing something with these bytes of data.

The bytes are NOT consecutive (see above)
Each byte encodes the data type for me to keep count of the number bytes for each source.

Then there are other considerations such as that first byte might not be located in the same input word. Once you know where the sync pattern ends, you could have anywhere from 0 to 8 bits of that first byte in that 32 bit word. Beyond that, the number of bytes in a particular message is not fixed so then you have to decode the first byte to figure out the length. Once you do have the message decoded, then what do you do with it?

See first answer



So, you can either try to describe the entire processing flow, or maybe just the area that is actually giving you the problem right now. I'm guessing that your issue right now is
- How to find the location of the end of the sync pattern (Possible solution would be the 'Find_First_Zero' function that I described).
- How to shift the input data the proper number of times in order to be able to decode the message (Solution is a barrel shifter, likely a pipelined barrel shifter but not necessarily).

Do you have an example of a pipeline barrel shifter

thanks
 
Last edited:

troy99xx said:
The sync pattern is a guarantee that the next data msg detected is the first byte of that of the data packet. It is to be sure that the device receiving the data is in sync
Click to expand...

Perhaps a little off topic, but if you are planning to send this pattern at the physical layer, do not seems a good choice. A single 1-bit change at the bound of a steady level could be enough to make a false detection.
 

troy99xx said:
After the sync pattern, it could be the next clock or 1000’s of clocks before the first byte of a data packet appears on the bus ( the interface will keep sending all 0xFF meanwhile).
Click to expand...
If the interface is sending FFs after the sync pattern until it actually has the message data, then the sync pattern will show up again. So now while you've already detected the sync pattern and have been "guaranteed that the next data msg detected is the first byte of that of the data packet" you've also just received another sync pattern which seems to have shot that guarantee you mentioned all to shreds. Sounds like either you're not describing the protocol correctly, or it is a protocol that needs some more thought put into it.

The bytes are NOT consecutive (see above)
Click to expand...
See my response to above as well.

Do you have an example of a pipeline barrel shifter
Click to expand...
The shift_right and shift_left functions that are a part of ieee.numeric_std are good examples of an unpipelined shifter. You give the function your vector and a count of how many bits you'd like to shift and it returns the result. The problem you will face is that (last I looked), synthesis tools choked if the number of bits you told it to shift was not a constant. The way to work around it is to break it down into shifts that are constants. By looking at a particular bit in what you've computed to be the amount of the shift, you'll know if you should shift or not. For example,
Code: 
signal x: unsigned(31 downto 0);
signal Shift_Bits: natural range x'range;
...

process(Clock)
begin
   if rising_edge(Clock) then
      if (Shift_Bits(4) = '1') then
         x1 <= shift_right(x, 16);
      else
         x1 <= x;
      end if;

      if (Shift_Bits(3) = '1') then
         x2 <= shift_right(x1, 8);
      else
         x2 <= x1;
      end if;
      ...
      if (Shift_Bits(0) = '1') then
         x5 <= shift_right(x4, 2);
      else
         x5 <= x4;
      end if;
   end if;
end process;
x5 will then hold the fully shifted output

Kevin Jennings
 

K-J said:
If the interface is sending FFs after the sync pattern until it actually has the message data, then the sync pattern will show up again. So now while you've already detected the sync pattern and have been "guaranteed that the next data msg detected is the first byte of that of the data packet" you've also just received another sync pattern which seems to have shot that guarantee you mentioned all to shreds. Sounds like either you're not describing the protocol correctly, or it is a protocol that needs some more thought put into it.
Click to expand...

Kevin, I think you are over analyzing this. I get the impression the 0xFFFF_FFFF is the sync pattern being searched for, once found the input logic starts looking for the start of data which starts at the first byte (32-bit aligned) that is not 0xFF. I'm assuming there is either some header or a constant length that is used for the packet payload that is sent. The input logic will therefore work similarly to the synchronization of a Ethernet link where it synchronizes to the preamble but doesn't care if the payload has the preamble sequence embedded in it.
 

Status
Not open for further replies.

Similar threads

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Back
Top