Sampling and Reconstructing Digital Signal

Question

Say that I have a digital signal (a bitstream actually) whose output changes every 100 mS. I don't know exactly when it changes relative to my sampling, only that that the next bit to capture appears after 100 mS. (I'm not capturing a square wave, but rather the signal might or might not assume a new value (either 1 or 0) after 100 mS.) So I sample the signal every 25 mS. How do I reproduce the bitstream from the sampled stream over some period of time...I can miss the first few bits of the capture, but after that I want to get every bit of the output? I assume that there is a common algorithm for doing this.

By the way, the solution can all be done in software (Java / C++) and does not have to be real time...I can collect all samples and then post-process it to extract the signal.

Answer 1

If the two clocks have not too much drift between them and the bit stream has edges often enough, you can do it like this:

Dots are samples taken every 25 ms, and the continuous line represents what is known about the timing of the binary signal that changes every 100 ms based on the first synchronization. Ambiguity is represented by multiple possible edge times. Synchronization happens when a sample has a different value than the previous one. Then you know that the edge is somewhere between the current (blue) sample and the previous sample. The next two samples (green) are good as you know which bit of the signal they represent, but the two samples following those are bad, because if there is even a tiny bit of drift (visualized as spreading of the possible edge times) between the clocks, you won't know if they represent the current bit or the next bit.

You continue repeating: good sample, good sample, bad sample, bad sample, until you encounter another edge and can resynchronize. You can use any one of successive good samples to reconstruct the bitstream. Actually the blue edge samples are good to use too, but who cares.

Answer 2

Yes, there is. You have to study a broad field in digital communication systems which is called synchronization. Generally speaking, much of the synchronization principles are the same across different parameters. Specifically, you need to implement a timing synchronization (also called timing recovery or clock recovery) subsystem in a digital receiver. You can do it in either in open loop manner (feedforward) or closed loop method (feedback, PLL based). Once you start implementing it, then you will have specific questions for which you can return to SE time and again.

In this particular example, your clock frequency is all right (bits are changing every 100ms --- a constant difference from your sampling intervals). Ideally, the output of a matched filter is sampled at the end the sampling period. Since you don't know the ideal sampling instants (maximum eye opening), you have to use either the knowledge of the data (say, a preamble), or you can use characteristics of your bitstream in a non-data-aided manner.

Edit: If you are sampling at 25ms, that makes your samples/symbol equal to 4. If post processing is not an issue, then just use digital filter and square timing recovery for the whole preamble. the closed form expression gives you an exact estimate of timing phase offset.

Then, you will have to interpolate your data according to the estimate obtained above and downsample the signal from 4:1.

Answer 3

I came up with a simple solution in Java that was able to reconstruct the bit stream using 3x over-sampling. The example below involves 2 signals, but that's not part of the problem statement.

import java.util.LinkedList;
import java.util.Queue;

public class SampleQueue {
private double oversampleratio;
private Queue<Character> output;

public SampleQueue(double oversampleratio) {
    this.oversampleratio = oversampleratio;
    this.output = new LinkedList<Character>();
}

public char[] process(String sampled) {
    char currentchar = sampled.charAt(0);
    int charcounter = 0;
    for(int i = 0; i < sampled.length(); i++) {
        if(currentchar == sampled.charAt(i)) {
            charcounter++;
        }
        else {
            process(currentchar, charcounter);
            charcounter = 1;
            currentchar = sampled.charAt(i);
        }
    }
    if(charcounter > 0) {
        process(currentchar, charcounter);
    }
    return getString();
}

private char[] getString() {
    int length = output.size();
    char[] str = new char[length];
    for(int i = 0; i < length; i++) {
        str[i] = output.poll();
    }
    return str;
}

private void process(char currentchar, int charcounter) {
    int actualsamples = (int) Math.round(charcounter / (double) oversampleratio);
    for(int i = 0; i < actualsamples; i++) {
        output.add(currentchar);
    }
}
}


import org.apache.commons.lang3.StringUtils;

public class DataAndClockSignal {
    private double phase;
    private double sampleperiod;
    private String data;
    private String sampleddata;
    private String clock;
    private String sampledclock;
    private int clocklevel;

public DataAndClockSignal(double phase, double sampleperiod) {
    this.clocklevel = 0;
    this.phase = phase;
    this.sampleperiod = sampleperiod;
    this.data = "";
    this.clock = "";
    this.sampledclock = "";
    this.sampleddata = "";
}

public void generateRandomSamples(int numsamples) {
    MersenneTwisterFast mtf = new MersenneTwisterFast();
    int maxvalue = (int) Math.pow(2, 12);
    int generatedsamples = 0;
    while(generatedsamples < numsamples) {
            for(int i = 0; i < 10 + mtf.nextInt(25); i++) {
                addData(mtf.nextInt(maxvalue));
                generatedsamples++;
            }           
    }
    dump();
}


public void addData(int dataint) {
    String str = Integer.toBinaryString(dataint);
    data += StringUtils.leftPad(str, 12, '0');
    transitionClock();
    if(clocklevel == 0) {
        clock += "000000000000";        
    }
    else {
        clock += "111111111111";
    }
}

private void transitionClock() {
    clocklevel = (clocklevel + 1) % 2;
}

public void dump() {
    sampledclock = "";
    sampleddata = "";
    double sampletime = phase;
    for(int i = 0; i < data.length(); ) {
        sampledclock += clock.charAt(i);
        sampleddata += data.charAt(i);
        sampletime += sampleperiod;
        i = (int) sampletime;
    }
    System.out.println("Clock:            " + clock);
    System.out.println("Data:             " + data);
    System.out.println("SampledClock: " + sampledclock);
    System.out.println("SampledData:  " + sampleddata);
}

public String getData() {
    return data;
}

public String getSampleddata() {
    return sampleddata;
}

public String getClock() {
    return clock;
}

public String getSampledclock() {
    return sampledclock;
}

public static void main(String[] args) {
    DataAndClockSignal randomsig = new DataAndClockSignal(0.37, 0.34);
    randomsig.generateRandomSamples(500);
    }
}


public class Reconstruction {
private String data;
private String clock;
private double sampleperiod;

public Reconstruction(double sampleperiod) {
    this.sampleperiod = sampleperiod;
}

public void processRandomData(double timeoffset) {
    DataAndClockSignal dataandclock = new DataAndClockSignal(timeoffset, sampleperiod);
    dataandclock.generateRandomSamples(500);
    data = dataandclock.getData();
    clock = dataandclock.getClock();
    char[] reconstructeddata = reconstruct(dataandclock.getSampleddata());
    char[] reconstructedclock = reconstruct(dataandclock.getSampledclock());
    System.out.print("Reconstructed Clock: ");
    System.out.println(reconstructedclock);
    System.out.print("Reconstructed Data: ");
    System.out.println(reconstructeddata);  
    if(new String(reconstructeddata).equalsIgnoreCase(data)) {
        System.out.println("Data matches!");
    }
    else {
        System.out.println("Data does not match!");
    }
    if(new String(reconstructedclock).equalsIgnoreCase(clock)) {
        System.out.println("Clock matches!");
    }
    else {
        System.out.println("Clock does not match!");
    }
}

private char[] reconstruct(String sampled) {
    SampleQueue samplequeue = new SampleQueue(1 / sampleperiod);
    return samplequeue.process(sampled);
}

public static void main(String[] args) {
    double sampleperiod = 0.34;
    double timeoffset = 0.37;
    Reconstruction reconstruction = new Reconstruction(sampleperiod);
    reconstruction.processRandomData(timeoffset);
}

}