What is the right terminology / methods for this standard signal processing task?

Question

Say we have a signal s = [1,2,2,1,3,3,2,2,1,1] or similar (only 1,2,3 can occur). I want to look for a particular pattern, e.g. [1,3,3,2], which can occur anywhere (0 or many times) in the signal. I would like to perform the computation as a convolution with some filter f.

I've convinced myself that f = [100,1000,1000,10] will do the job, i.e. sending the pattern p = [1,3,3,2] to f = 10.^fliplr(p), in matlab syntax. That is, the convolution s*f will take the value 1*10 + 3*1000 + 3*1000 + 2*100 = 6210 if and only if we have the pattern p in the right place, at least as long as the pattern we are looking for is short enough.

For a long enough pattern, e.g. [1,1,1,1,1,1,1,1,1,1,2] (ten 1s followed by a 2), the corresponding filter f = [100,10,..,10] would give a "false positive" for the pattern [2,2,2,2,2,2,2,2,2,2,1], since the convolution would give the values 10*10 + 2*100 = 300 for the first, and 2*10*10 + 1*100 = 300 for the second. (That I needed 10 1s to "trick" the filter is obviously related to the fact that my filter "encodings" of the 1s and 2s differ by a factor 10. Changing the encoding to e.g. {1,2,3} -> {10,1000,100000} should let me handle correspondingly longer patterns).

I have a strong feeling that this is a very standard signal processing task. What is the standard terminology and methods concerning this problem? (I.e. what key words should I google.)

Answer 1

The thing you are looking for is the matched filter, which is essentially the (optimal) linear approach to look for a known pattern in a signal (which may be impacted by additive zero mean noise).

The impulse response (i.e., the sequence you are convolving with) of the matched filter is just the pattern reversed, i.e. $f = [2, 3, 3, 1]$ will do the job. If the input signal is normalized in RMS amplitude, the matthed filter will give maximum output if and only if the pattern occurs.

Answer 2

Assuming that the pattern $x$ you are looking for consists of $L$ samples (in your example, $x \in \{1,2,3\}^L$), the filtering operation with a filter of length $L$ essentially performs a weighted average of all length-$L$ sequences of the incoming signal with a weighting vector $w \in \mathbb{R}^L$. Therefore, if you want perfect detection, the following condition should hold $$ w^T x \neq w^T y, \text{ for all } y \in \{1,2,3\}^L, y \neq x. $$

The above set of equation can be compactly written as $$ A^Tw=b $$ where $A$ is an $L\times (3^L-1)$ matrix with columns equal to $x-y$, for all $y \in \{1,2,3\}^L, y \neq x$, and $b \in \mathbb{R}^{3^L-1}$ is a column vector with non-zero elements.

Your problem, therefore, boils down to finding such a $w$ (and $b$). Unfortunately, I am not aware of a systematic way to do this (someone else might). You could also try asking the signal processing SE.