DSP - BLOCK AUTOCORRELATION

Introduction link

The Block Autocorrelation block chops the input stream into consecutive blocks of N samples and, at the end of each block, publishes the autocorrelation coefficient of that block at a lag k:

$$ \rho(k) = \frac{\sum_{i=k}^{N-1} (x_i - \mu)(x_{i-k} - \mu)} {\sum_{i=0}^{N-1} (x_i - \mu)^2}, \qquad \mu = \frac{1}{N}\sum_{i=0}^{N-1} x_i $$

This is the standard biased sample autocorrelation coefficient: $\rho(0) = 1$ exactly, $|\rho(k)| \le 1$, and it is dimensionless and gain independent - amplify the signal and $\rho$ does not move.

THE MEAN IS REMOVED, and that is the point link

An autocorrelation taken on the raw samples is dominated by the DC level: a signal sitting on a pedestal correlates with itself at every lag simply because it is positive, and the answer is a slab near 1 that tells you nothing. Subtracting $\mu$ - the mean of the same block - makes $\rho(k)$ answer the question actually being asked: is there structure at this lag?

You do not have to remove the baseline upstream, and you must not: the block removes the mean of the block it is reporting on, which is the right mean even if the baseline drifts from block to block.

THE LAG IS A PIN, not a property link

LAG is a 6 bit input, so a design can sweep it - one block per lag - and reconstruct the whole correlogram $\rho(1), \rho(2), \ldots$ without rebuilding the IP. That is what makes this block a measurement instrument rather than a fixed filter:

• drive LAG from a counter and you get a correlogram at one lag per block;
• drive it from a register interface and a CPU can hunt for a period;
• hold it fixed and you get a single-lag monitor for free.

LAG is latched on the first sample of each block, exactly like EXP, so a block is never accumulated at one lag and reported at another. It is clamped to the Max Lag property, which is what sizes the delay line.

N is a runtime input too link

You drive the exponent on the EXP pin and the block size is $N = 2^{\mathrm{EXP}}$:

The table starts at 256 on purpose: this block has a serial tail of well over a hundred clocks. See “The serial tail”.

How to read the answer link

Sweep LAG and look at the shape:

A correlogram is also the cheapest period estimator that does not need an FFT: find the first $k > 0$ at which $\rho$ peaks.

What it is FOR link

• period / pitch detection on a channel with no threshold to speak of;
• noise characterisation: is my noise white, or is it filtered? $\rho(1)$ alone answers that;
• oversampling and effective bandwidth checks on a digitiser chain;
• pile-up / after-pulse hunting in pulse processing - an after-pulse at a fixed delay shows up as a bump at that lag;
• vibration monitoring, where a periodic component appearing in the correlogram is a bearing or a gear mesh.

Cost link

Per clock, while accumulating: two multipliers ($x^2$ for the power sum and $x \cdot x_{i-k}$ for the lagged product), four accumulators and the only memory in the block - a Max Lag-deep delay line, which is a shift register (an SRL on Xilinx), not a RAM.

There is no second pass and no sample buffer: the block never re-reads the samples. An exact integer identity (below) collapses the centred products into raw power sums plus one small correction, so all the block has to remember is the last Max Lag samples. Compare that with Block Mean Abs Deviation, which really does have to store the whole block and therefore runs at half rate.

In the tail: one reused shift-add stage driven through three multiply passes, and one restoring divider. No DSP in the tail.

When to use this instead of Block Statistics link

The all-in-one Block Statistics block is not deprecated, but it does not compute an autocorrelation: it has no delay line and no lagged-product accumulator, so there is no counterpart to this statistic over there. The usual rule still applies to everything else you may want from the same data:

• you want several statistics of the SAME block - mean and RMS and min/max of the same N samples - use Block Statistics. They share one accumulator and one serial tail, so the second and third statistic are nearly free.
• you want exactly one number - use a per-operator block. Then you synthesise only that number, and nothing else reaches the synthesiser.

A Block Variance placed next to this one will duplicate the $S_1$ / $S_2$ accumulators this block already keeps internally. That is two adders’ worth of duplication and it is not a reason to avoid either block.

Pin Description link

Properties link

The exact-integer identity: why there is no second pass link

Expanding the centred products and clearing the denominators turns the definition into arithmetic on raw power sums, which can all be accumulated in one streaming pass. With

$$ S_1 = \sum_{i} x_i, \qquad S_2 = \sum_{i} x_i^2, \qquad S_{xy} = \sum_{i \ge k} x_i , x_{i-k}, \qquad P_2 = S_1^2 $$

and $S_{ed}$ the sum of the two end runs - the $k$ samples the shifted copy loses off the front and the $k$ it loses off the back,

$$ S_{ed} = \sum_{i < k} x_i ; + \sum_{i \ge N-k} x_i $$

the two lagged windows have sums $S_1 - \text{head}$ and $S_1 - \text{tail}$, so everything collapses to

$$ \mathrm{num} = N^2 S_{xy} - N P_2 + N S_1 S_{ed} - k P_2, \qquad \mathrm{den} = N,(N S_2 - P_2), \qquad \rho = \frac{\mathrm{num}}{\mathrm{den}} $$

Every $N\cdot$ and $N^2\cdot$ is a shift (N is a power of two). ONE end-run accumulator replaces the two separate window sums. The only term that is not a shift of a product is $k P_2$ - and $k \le 63$, so that multiply is six serial steps, not $\mathrm{IN_SW} + \mathrm{EXP}$ of them.

Note $\mathrm{den} = N \times$ the variance numerator that Block Variance computes, which is why a constant block falls out correctly: $\mathrm{den}$ is 0, $\mathrm{num}$ is 0 as well (every centred product vanishes), and the zero-denominator path reports 0.

Accuracy link

The magnitude of the quotient is floored to AUTOCORR Fractional Bits and the sign is applied afterwards. Everything before that division is exact integer arithmetic - no accumulated rounding, no truncated intermediate.

The host regression (tb/block-ops/run_tb.ps1) therefore demands tolerance ZERO against a Python golden (tb/block-ops/gen_golden.py) that evaluates the centred definition in exact rational arithmetic and floors it the same way - not “within 1 LSB”, not “within a few counts”. Any deviation at all fails the build.

The two corner cases link

LAG = 0 gives rho = 1 EXACTLY, and it is NOT special cased link

With $k = 0$ the delay line is bypassed - $x_{i-0}$ is the sample itself - and the identity degenerates: the numerator becomes the denominator, term for term, and the quotient is exactly $1.0$, i.e. 16384 in the default Q2.14.

There is no if (lag == 0) anywhere in the core. The arithmetic reaches the right answer on its own, which makes LAG = 0 a free self test on live hardware: drive it and the output must read exactly $2^{\mathrm{ACF_{fract}}}$. If it does not, something upstream - the input format, the IN_DV timing, the block framing - is wrong, and you have found out without a simulator.

LAG >= N forces the output to 0, and that one IS a real guard link

If the lag is at least as long as the block, the block and its shifted copy do not overlap at all: there is nothing to correlate. The identity above is only valid for $0 \le k \le N$, so this case is detected and the output is forced to 0 - it is a genuine guard, not a formality.

In a correctly sized design you cannot reach it: LAG is 6 bits and clamped to Max Lag (63 at the very most), while the minimum usable EXP for this block’s tail is already 7 or 8, i.e. $N \ge 128$. It only becomes reachable if you drive EXP below the minimum the compiler printed - in which case most of your results are being dropped anyway (see below). The regression exercises it exactly that way, on purpose.

Sweeping the lag link

LAG is sampled on the first accepted sample of a block and held for that whole block, so a change takes effect on the next block that STARTS. On a gapless stream the next block starts on the very next clock after the previous one ended - which is before the previous block’s OUT_DV, because the tail is long. Two consequences worth planning for:

• do not update LAG from OUT_DV and expect the very next result to use it. By the time OUT_DV for block n pulses, block n+1 has already latched its lag; your new value lands on block n+2. Keep a small shadow register chain of the lag values you drove, and pair each OUT_DV with the right one.
• or make it unambiguous by dropping IN_DV between blocks: with the stream gated off during the tail there is only ever one block in flight, OUT_DV arrives before the next block starts, and “update LAG on OUT_DV” does exactly what it looks like. You pay one block period of throughput per point of the correlogram.

Either way the value is always self-consistent: a block is never accumulated at one lag and reported at another.

Accumulation and IN_DV link

IN_DV is the only qualifier. It says “this clock carries a sample”: the sample is squared into $S_2$, added to $S_1$, multiplied by the delayed sample into $S_{xy}$ when the shifted copy still overlaps, added to $S_{ed}$ when it falls in an end run, shifted into the delay line, and counted towards N - exactly on the clocks where IN_DV is high. Clocks with IN_DV low are ignored completely, including by the delay line: whatever sits on IN during them cannot corrupt the block and cannot displace the lagged sample. The serial tail keeps running regardless, which is what you want.

(The delay line is deliberately not cleared at a block boundary. It never needs to be: $S_{xy}$ only takes a pair whose partner is inside the same block.)

Unconnected, IN_DV ties to '1', EXP ties to 10 (N = 1024) and LAG ties to 1 - the shortest meaningful lag, so an unwired block reports the one-sample correlation rather than the trivial $\rho(0) = 1$.

There is deliberately no CE pin. On the all-in-one Block Statistics block an earlier revision had one, and it did not survive synthesis: with nothing but internal state gated by it, Vitis could reason the frozen path away and delete the port from the generated entity while SciCompiler’s wrapper still wired it, which failed a real Vivado build with [VRFC 10-718] formal port <ce> does not exist in entity. The whole per-operator family was built without one. To stall this block, gate its IN_DV - a block that only accumulates on IN_DV has no need to be frozen, and there is no reason to stall the tail.

When EXP changes link

EXP is clamped to Max Block Exponent and then latched on the first accepted sample of a block, and held for that whole block - and so is the “does the lag still overlap?” decision that depends on it. A change therefore takes effect on the NEXT block: a block in progress always finishes against the N it was started with, and a block is never emitted against a different N than the one it was accumulated with. Remember that EXP also has to satisfy $2^{\mathrm{EXP}} \ge L$ at run time, every time.

Timing: the serial tail link

The latency contract link

OUT_DV pulses for one clock when the tail COMPLETES, L clocks after the clock on which the N-th sample of the block was accepted - not when that sample arrives. AUTOCORR is updated on that same clock and on no other. The state walk is

  IDLE -(go)-> MUL2 x (IN_SW+EXP) -> MULE x SEW -> MULK x 6
          -> VAR -> CLD -> DIV x CNUMW -> FIN -> IDLE
  

• the three multiply passes being $|S_1|\cdot|S_1|$, $|S_1|\cdot|S_{ed}|$ and $P_2 \cdot k$ - with OUT_DV registered, so

$$ L = (\mathrm{IN_SW} + \mathrm{EXP}) + \mathrm{SEW} + 6 + 1 + 1 + \mathrm{CNUMW} + 1 + 1 $$

with the widths fixed at compile time by your formats:

$$ \mathrm{SEW} = \mathrm{IN_SW} + 7 $$

$$ \mathrm{MW} = \max\bigl(2,\mathrm{IN_SW} + 3,\mathrm{MaxBlockExponent},; 2,\mathrm{IN_SW} + 2,\mathrm{MaxBlockExponent} + 7 \bigr) + 2 $$

$$ \mathrm{CNUMW} = \max\bigl(\mathrm{MW} + \mathrm{ACF_{fract}},; \mathrm{AUTOCORR\ width} + 2\bigr) $$

where $\mathrm{IN_SW}$ is the signed working width of a sample: the input width, +1 if the input is UNSIGNED.

What each knob costs, in clocks link

For any Max Block Exponent of 7 or more (where the first term of MW wins) this collapses to

$$ L = 4,\mathrm{IN_SW} + 3,\mathrm{MaxBlockExponent} + \mathrm{ACF_{fract}} + \mathrm{EXP} + 19 $$

Two things are worth calling out:

• Max Lag costs no clocks at all. It buys delay-line registers and nothing else - the $P_2 \cdot k$ pass is always six steps, whatever the lag is. Ask for the deepest lag you want to sweep to; it is the cheap knob here.
• The tail depends on the runtime EXP only through the $|S_1|^2$ pass, one clock per unit - much gentler than Block Correlation’s three.

Worked numbers link

For the default configuration - IN Q16.0 SIGNED ($\mathrm{IN_SW} = 16$), Max Block Exponent 20, Max Lag 16, AUTOCORR Q2.14 SIGNED:

• $\mathrm{SEW} = 16 + 7 = 23$
• $\mathrm{MW} = \max(32 + 60,\ 32 + 40 + 7) + 2 = 94$
• $\mathrm{CNUMW} = \max(94 + 14,\ 16 + 2) = 108$
• $L = (16 + \mathrm{EXP}) + 23 + 6 + 1 + 1 + 108 + 1 + 1 = \mathbf{157 + \mathrm{EXP}}$

so at EXP = 10 the tail is 167 clocks and at the worst case EXP = 20 it is 177 clocks. The smallest usable exponent is the smallest EXP with $2^{\mathrm{EXP}} \ge 157 + \mathrm{EXP}$:

• EXP = 7: $128 \ge 164$? no
• EXP = 8: $256 \ge 165$? yes - so EXP $\ge$ 8, i.e. N $\ge$ 256

A few configurations:

There is also a floor on Max Block Exponent itself: with a 16 bit signed input at Q2.14, a Max Block Exponent of 6 or less is refused by the property page, because the minimum usable exponent would then be larger than the largest block the accumulators are sized for.

The 2^EXP >= L rule, and what happens when it is broken link

The tail of one block must finish before the next block completes:

$$ 2^{\mathrm{EXP}} \ge L $$

If a block completes while the previous tail is still running, that block’s result is DROPPED: there is no OUT_DV for it, the accumulators and the delay line are unaffected and the following blocks come out correctly, but a result is silently skipped. There is no error pin and no overrun pin for it.

The property page refuses a configuration whose minimum exponent exceeds Max Block Exponent, and CompileHDL prints both numbers - the worst case tail length and the minimum usable EXP - in the compilation log, so the static half of the problem is caught for you.

But EXP is a PIN. With $L$ well over a hundred clocks, an EXP of 6 - a perfectly ordinary value on Block Mean - drops every result here, with no symptom other than an OUT_DV that never pulses. It is also the only way to reach the LAG >= N case. If EXP is under software control, clamp it in software to the minimum the compiler printed, and enable SAMPLE_COUNT if you want to confirm the block length at run time.

Knowing where the block is: BUSY, INTEGRATING and SAMPLE_COUNT link

Three optional status outputs, all defaulting to NO. They answer different questions, and on this block the difference matters because the tail is long:

Every output of this block is a register, so each status bit is observed on the clock after the event that sets it:

• INTEGRATING rises on the clock after the FIRST sample of a block is accepted and falls on the clock after the N-th - it is high exactly while the block is ACCUMULATING. BUSY high with INTEGRATING low is the three-products-then-divide tail.
• BUSY covers the accumulation and the tail. It rises with INTEGRATING, stays high across the tail, and its LAST HIGH CLOCK IS THE OUT_DV PULSE; it falls on the clock after.
• On a continuous stream the next block starts before the previous tail ends, so BUSY never drops and INTEGRATING dips for exactly one clock per block boundary - which makes it a free block marker, and the right thing to count if you are sequencing a lag sweep.
• SAMPLE_COUNT is a fixed 32 bits and reads 1 after the first accepted sample, N after the N-th. It is NOT cleared at the block end: it HOLDS N through the tail and past OUT_DV, until the first sample of the next block takes it back to 1. so it reads N at OUT_DV only when the input STOPS for the whole tail; on a CONTINUOUS stream the next block has already started and OUT_DV shows how far into it you are. The clock that always reads N is the one INTEGRATING falls on - the useful thing to latch alongside the result, and the cheapest run-time confirmation that the block was long enough for the tail. Only RESET clears it to 0.

Q formats link

IN and AUTOCORR carry their own fixed point format (integer bits, fractional bits, sign), the same convention as the Fixed P. family.

Sizing AUTOCORR is easy, because the range is known:

• $|\rho| \le 1$, so two integer bits are enough for the value AND its sign - that is the default, and $+1.0$ lands exactly on $2^{\mathrm{ACF_{fract}}}$, i.e. 16384 in Q2.14;
• every remaining bit buys resolution: the default 14 fractional bits give steps of $1/16384 \approx 6\times10^{-5}$, at one clock of tail each;
• SIGNED is the default and should stay that way - a negative $\rho$ (alternating samples, or the trough of a periodic correlogram) is real information, and an UNSIGNED format clamps every negative lag to 0, which would flatten exactly the features you are looking for.

The input fractional bits do not affect the value: $\rho$ is a ratio of two quantities with the same units, so the scalings cancel.

Note that the quotient already comes out at AUTOCORR fractional bits, so the final requantisation has nothing to shift. The Rounding property therefore has no effect on this block’s value; only Saturation still applies, and only if you choose a format narrower than the $[-1,+1]$ range needs.

Verification link

The core is regression tested by a host-side csim harness (tb/block-ops/run_tb.ps1) that runs one simulated clock at a time and follows OUT_DV. The expected values come from tb/block-ops/gen_golden.py, which evaluates the centred definition in exact rational arithmetic - deliberately not the raw-moment identity the core uses, so the two share no algebra - and the tolerance is 0.

The tail length is checked against the formula at compile time: three copies of it exist - the BAC_TAIL macro in the core, tail_len() in the generator and TailClocks() in the plugin - and the testbench refuses to build if they disagree. tb/block-ops/port_check.py preprocesses the real core and checks the symbol’s pin list against the generated entity’s ports for every enable combination. The status outputs are checked clock by clock against the contract above. There is no all-in-one counterpart to cross-check against - Block Statistics has no autocorrelation - so the exact-rational golden is the only reference, which is why its tolerance is zero.