Sampling and Reconstructing Digital Signal 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.
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.