0
$\begingroup$

Suppose $D$ is a string of length $L$ where its values are uniformly distributed in $[-a,a]$. Also, all values of $D$ are independent (i.i.d).

$X$ is a noisy version of $D$ in this way: $X=D+N$ where $N$ is a white Gaussian noise with mean and variance of $0$ and $\sigma_N^2$.

$P$ is a sub-string of $D$ where its length is $l$ $(l<L)$.

To detect $P$ in $X$, I use the cross-correlation of $X$ and $P$: $$ C_n = \sum_{i=1}^l X_{n+i-1}P_i \space\space , \space\space 1<n<L-l+1 $$ and a threshold of $T=K\sigma_{C_n}$ where $K$ is a constant value and $\sigma_{C_n}$ is the standard deviation of the correlation signal $C_n$.

A false negative occurs If no points of the correlation signal reaches the threshold.

Now the question is: how can I theoretically calculate the false negative probability? It tried to use Q-function, but I couldn't achieve the answer.

$\endgroup$
  • $\begingroup$ geepers i love it to see a "new contributor" making use of $\LaTeX$ in what might appear to be their very first post. $\endgroup$ – robert bristow-johnson Feb 26 at 5:40
  • $\begingroup$ however i might recommend counting from 0 in your summation. and in your vector (or "string") indices. $\endgroup$ – robert bristow-johnson Feb 26 at 5:42
0
$\begingroup$

"Suppose $D$ is a string...".

No it is not.

Because if this were a string (a discrete sequence), then its content would take values from an alphabet of symbols, say $A \in \left[0 \dots (b-a) \right]$ where $b,a \in \mathbb{N}, b>a$ with some uniform discrete probability $\mathcal{U}(0,|A|)$, where $|\cdot|$ denotes the length of the sequence. Then, the operation of correlation would not make sense and we would have to use an appropriate string "similarity" function. For example, the hamming distance. Then, we would accept an error rate, which would represent the number of symbols set in "error" by some noise process. In ideal conditions, the normalised hamming distance (the sum of all symbols in error in a sequence divided by the length of the sequence) would be $0$ and as the error rate increased, so would the hamming distance all the way to $1$ in which case we would miss the entire sequence.

But that is not what is implied here. What is implied here is that $D \in \mathbb{R^k}$ (where $k$ here denotes the length of $D$), it takes values from a continuous $\mathcal{U}(a,b)$ and these represent the "message". This message is then contaminated by additive white gaussian noise to produce $X$. Then, we try to correlate a rolling window (of finite width) of $D$ over $X$ and observe the amplitude of the correlation at each "window shift" ($C_n$).

So, given that former framework where $D \in \mathbb{R}$:

The first step in modelling this is to look at what is the output exactly. The output is something like "What is the probability that the amplitude of correlation makes (or does not make) the threshold?". Without knowing anything else about the amplitude of each correlation ($C_n$), its value can swing anywhere $\in \left[-1 \dots 1 \right]$. So the probability there is some $p \in \mathcal{U}(-1,1)$. Not very useful yet.

Under ideal conditions (no noise), we would expect the correlation to correctly recognise the subsequence every time. So, if $P$ was repeating in $X$, $C_n=1$.

In the presence of additive white gaussian noise, the correlation amplitude is reduced (+). And, not only $C_n$ is reduced but any estimate of $n$ (where the sequence was detected, the $n$) is becoming uncertain too.

Additive white Gaussian noise is kind of special because its correlation with anything is $0$. So, if you had something like $Z_{\alpha} = \alpha \cdot X + (1-\alpha) \cdot \mathcal{N}(0,\sigma)$, then the correlation of $Z_1, Z_0$ is $0$. Another way to look at $\alpha$ is as (a variable proportional to) the signal to noise ratio (SNR). The lower the $\alpha$ the more noise you get in the signal, the more noise you get in the signal, the lower the correlation amplitude gets, the lower the correlation amplitude gets, the harder it is for it to reach the threshold.

What is the lowest value the correlation can attain?

It is zero. (If it gradually went towards $-1$, ....that would be spooky).

When will the correlation be zero?

When the noise will be at its maximum.

When is the noise at its maximum?

...it depends on the relative power between the noise and the signal. In other words, all things being equal, $\alpha$ depends on the length of $D$ to achieve the same SNR (but scaled up, to account for the fact that a sequence is now longer). For more details about this, you might want to have a look at this.

Long story short, this now brings us to the bit error rate curves. The theoretical bit error rate curves tell you how many symbols in error you are expected to get given the power SNR. These are also relevant here because at the end of the day, you are also making a binary decision. You either detect $P$ or you don't.

But, all that you have to do here is to adjust your $E_b/N_0$ for the lengths of the sequences you are looking for because in your case, your "bit" is the whole sequence $P$.

What is the theoretical expression for bit error rate?

$$BER = \frac{1}{2} \text{erfc}\left(\sqrt{\frac{E_b}{N_0}}\right)$$

Where $\text{erfc}$ is the error function. For more details on BER, see here

This $BER$ will tell you what you are after, that is, what is the probability that I miss a $P$ when it is there, given a particular SNR.

Hope this helps.

Notes:

+: The correlation has a finite range $\in \left[-1 \dots 1\right]$. Therefore, saying "...the standard deviation of the correlation signal..." is a misconception. This would be valid for something like $\mathcal{N}(0,0.2)$. But as the correlation tends to the edges of its range, this "...plus or minus..." of the standard deviation becomes invalid. When the conditions are such that the correlation hits $1$, there is no way its deviation will be anything else than $0$. So, perhaps this definition of the threshold as $K$ times the standard deviation of the correlation signal needs a bit more thinking depending on the problem at hand (?). I am assuming that it was defined in this way to then be able to determine a suitable value that guarantees detection.

$\endgroup$
  • $\begingroup$ Thanks @A_A. It's very hard for me, but I try to understand. However, One thing I should note is that actually the string values (that's to say the vector) are unifromly distributed in $[-a,a]$ (not $[a,b]$) $\endgroup$ – M.H Feb 26 at 10:52
  • $\begingroup$ @M.H Hi, glad to hear that this was somewhat helpful. On the limits, I took what was mentioned in the question. Perhaps it would be useful to edit it to include these discrepancies (?) and also what is it that you are trying to achieve (?) We might be able to address that directly. $\endgroup$ – A_A Feb 26 at 11:28
  • $\begingroup$ I edited the question. Actually I want a formula for the false negative probability of the explained procedure. $\endgroup$ – M.H Feb 26 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.