viernes, 31 de julio de 2015

Discrete signal denoising

Given a stream of bits, we need to find the change of state and it's length.
SIGNAL OUTPUT
  0            
  0            
  0            
  0            
  1    0(4)
  1            
  1            
  1            
  0    1(4)
  0            
  0            
  0            
  1    0(4)
  1            

Fig. 1: Stream of data unaffected by noise, 3 flanks detected
Unfortunately, some bits may be affected by noise.
SIGNAL NOISE READ OUTPUT
  0            0     
  0            0
  0      X     1  0(2) 
  0            0  1(1)
  1            1  0(1)
  1      X     0  1(1)
  1            1  0(1)
  1            1
  0            0  1(2)
  0            0 
  0      X     1  0(2)
  0            0  1(1)
  1            1  0(1)
  1            1

Fig. 2: Stream of data affected by 3 random bits, 9 flanks detected

This random bits of noise scramble our data. We need to remove them.

We define that a state transition will not count as such unless a certain threshold is reached.

A naive method for solving this would be to buffer the data in a long buffer, and then loop over it cleaning bits which not reach the threshold.

Instead, we propose a simple state machine.

We introduce a couple of concepts: Working state, Count and Threshold.

Now, insted of a long buffer and iterating over it, our state machine has a boolean variable and two counters. Here is an example of our algorithm in action.

READ WORK COUNT T_COUNT OUTPUT
  0    0    0     0      
  -    -    -     -      
  0    0    1           
  0         2           
  0         3           
  0         4           
  1               1       
  0         6           
  0         7           
  1               1       
  1               2       
  1    1    3             0(7) 
  0               1       
  0               2       
  1         6           
  1         7           
  1         8           
  0               1       
  0               2       
  0    0    3             1(8) 

Fig. 3: A noisy sample is denoised
Now a little python to test our algorithm
working = '0' 
count = 0 
transition = 0 
threshold = 2 
 
stream = "000010011100111000" 
for reading in stream: 
   if reading == working: 
       count += 1 
       if transition: 
           count += transition 
           transition = 0 
   else: 
       transition += 1 
       if transition > threshold: 
           print working, count # --> Called once per transition 
           count = transition 
           transition = 0 
           working = reading

#$python denoise.py
#0 7
#1 8

#Fig. 4: Denoise algorithm and it's output

No hay comentarios:

Publicar un comentario