title: Verilog: Minimal (hardware) algorithm for multiplying a binary input to its delayed form
body: <p>I have a binary input <code>in</code> (1 bit serial input) which I want to delay by <code>M</code> clock pulses and then multiply (AND) the 2 signals. In other words, I want to evaluate the sum:</p>
  
  <pre><code>sum(in[n]*in[n+M])
  </code></pre>
  
  <p>where <code>n</code> is expressed in terms of number of clock pulses.</p>
  
  <p>The most straightforward way is to store in a memory buffer <code>in_dly</code> the latest <code>M</code> samples of <code>in</code>. In Verilog, this would be something like:</p>
  
  <pre><code>always @(posedge clock ...)
      ...
      in_dly[M-1:0] &lt;= {in_dly[M-2:0], in}; 
      if (in_dly[M-1] &amp; in)
           sum &lt;= sum + 'd1;
      ...
  </code></pre>
  
  <p>While this works in theory, with large values of <code>M</code> (can be ~2000), the size of the buffer   is not practical. However, I was thinking to take advantage of the fact that the input signal is 1 bit and it is expected to toggle only a few times (~1-10) during <code>M</code> samples.</p>
  
  <p>This made me think of storing the toggle times from <code>2k*M</code> to <code>(2k+1)*M</code> in an array <code>a</code> and from <code>(2k+1)*M</code> to <code>(2k+2)*M</code> in an array <code>b</code> (<code>k</code> is just an integer used to generalize the idea):</p>
  
  <pre><code>reg [10:0]      a[0:9];     //2^11 &gt; max(M)=2000  and "a" has max 10 elements
  reg [10:0]      b[0:9];     //same as "a"
  </code></pre>
  
  <p>Therefore, during <code>M</code> samples, <code>in = 'b1</code> during intervals <code>[a[1],a[2]], [a[3],a[4]], etc</code>. Similarly, during the next <code>M</code> samples, the input is high during <code>[b[1],b[2]], [b[3],b[4]], etc</code>. Now, the sum is the "overlapping" of these intervals:</p>
  
  <pre><code>min(b[2],a[2])-max(b[1],a[1]), if b[2]&gt;a[1] and b[1]&lt;a[2]; 0 otherwise
  </code></pre>
  
  <p>Finally, the array <code>b</code> becomes the new array <code>a</code> and the next <code>M</code> samples are evaluated and stored into <code>b</code>. The process is repeated until the end of <code>in</code>.</p>
  
  <p>Comparing this "optimized" method to the initial one, there is a significant gain in hardware: initially 2000 bits were stored, and now 220 bits are stored (for this example). However, the number is still large and not very practical..</p>
  
  <p>I would greatly appreciate if somebody could suggest a more optimal (hardware-wise) way or a simpler way (algorithm-wise) of doing this operation. Thank you in advance!</p>
  
  <p><strong>Edit:</strong></p>
  
  <p>Thanks to Alexey's idea, I optimized the algorithm as follows:</p>
  
  <p>Given a set of delays <code>M[i] for i=1 to 10 with M[1]&lt;M[2]&lt;..&lt;M[10]</code>, and an input binary array <code>in</code>, we need to compute the outputs: </p>
  
  <p><code>y[i] = sum(in[n]*in[n+M[i]]) for n=1 to length(in)</code>.  </p>
  
  <p>We then define 2 empty arrays <code>a[j]</code> and <code>b[j]</code> with <code>j=1,~5</code>. Whenever <code>in</code> has a <code>0-&gt;1</code> transition, the smallest index empty element <code>a[j]</code> is "activated" and will increment at each clock cycle. Same goes for <code>b[j]</code> at <code>1-&gt;0</code> transitions. Basically, the pairs <code>(a[j],b[j])</code> represent the portions of <code>in</code> equal to 1. </p>
  
  <p>Whenever <code>a[j]</code> equals <code>M[i]</code>, the sum <code>y[i]</code> will increment by 1 at each cycle while <code>in = 1</code>, until <code>b[j]</code> equals <code>M[i]</code>. Once <code>a[j]</code> equals <code>M[10]</code>, <code>a[j]</code> is cleared. Same goes for <code>b[j]</code>. This is repeated until the end of <code>in</code>.</p>
  
  <p>Based on the same numerical assumptions as the initial question, a total of 10 arrays (<code>a</code> and <code>b</code>) of 11 bits allow the computation of the 10 sums, corresponding to 10 different delays <code>M[i]</code>. This is almost 20 times better (in terms of resources used) than my initial approach. Any further optimization or idea is welcomed!</p>