Frame synchronization

[Vladimir Vassilevsky]

In a couple of projects, I implemented frame synchronization based
entirely on the structure of the data and FEC; i.e. without insertion of
any preambles, sync markers or flags into the data stream. I even tried
to optimize FEC with respect to frame synchronization. That idea worked
nicely especially at low SNRs, although it can take a lot of computation.

The concept seems kind of obvious. Just wondering if there is any
relevant work in the literature; or if there are any practical
communication systems which use that approach.

Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

[Eric Jacobsen]

On 1/28/2010 10:16 AM, Vladimir Vassilevsky wrote:
>
> In a couple of projects, I implemented frame synchronization based
> entirely on the structure of the data and FEC; i.e. without insertion of
> any preambles, sync markers or flags into the data stream. I even tried
> to optimize FEC with respect to frame synchronization. That idea worked
> nicely especially at low SNRs, although it can take a lot of computation.
>
> The concept seems kind of obvious. Just wondering if there is any
> relevant work in the literature; or if there are any practical
> communication systems which use that approach.
>
> Vladimir Vassilevsky
> DSP and Mixed Signal Design Consultant
> http://www.abvolt.com

Sounds interesting to me. I'm not aware of any other systems that do that.

--
Eric Jacobsen
Minister of Algorithms
Abineau Communications
http://www.abineau.com

[Malachy Moses]

Others have at least thought about it, for example, U.S. Patent
6,560,745, "Method of identifying boundary of markerless codeword"
filed by the National Security Agency (NSA), issued in 2003.

A extracted quote from the patent:

"The present invention is a method of determining the starting bit
position of a codeword (i.e., the codeword boundary) that does not
require the use of marker bits to identify the codeword boundary. By
not including marker bits between codewords, codewords may be
transmitted in the fewest number of clock periods and, therefore, at
the maximum codeword transmission rate. Determining the codeword
boundary is useful for synchronization purposes (i.e., proper
identification, and decoding, of codewords). The present method
derives the codeword boundary from the codewords and not from marker
bits as does the prior art. "

Image of the patent available at
http://www.google.com/patents?id=BjgPAAAAEBAJ&printsec=abstract&zoom=4#v=onepage&q=&f=false

[steveu]

>
>In a couple of projects, I implemented frame synchronization based
>entirely on the structure of the data and FEC; i.e. without insertion o

>any preambles, sync markers or flags into the data stream. I even tried
>to optimize FEC with respect to frame synchronization. That idea worked
>nicely especially at low SNRs, although it can take a lot o
computation.
>
>The concept seems kind of obvious. Just wondering if there is any
>relevant work in the literature; or if there are any practical
>communication systems which use that approach.

Surely you always need something to latch onto. If you don't provid
specific sync bits, you have to provide enough redundancy in the bit strea
itself to be able to latch onto it. Isn't a perfectly white bit strea
something you could never decode?

Steve

[Vladimir Vassilevsky]

steveu wrote:
>>In a couple of projects, I implemented frame synchronization based
>>entirely on the structure of the data and FEC;

> Surely you always need something to latch onto.

Any kind of real world data provides a clue.

> If you don't provide
> specific sync bits, you have to provide enough redundancy in the bit stream
> itself to be able to latch onto it. Isn't a perfectly white bit stream
> something you could never decode?

Packed multimedia data looks very much like random bitstream, however
you can clearly distinguish a valid decode from invalid.


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

[steveu]

>
>
>steveu wrote:
>>>In a couple of projects, I implemented frame synchronization based
>>>entirely on the structure of the data and FEC;
>
>> Surely you always need something to latch onto.
>
>Any kind of real world data provides a clue.
>
>> If you don't provide
>> specific sync bits, you have to provide enough redundancy in the bit
stream
>> itself to be able to latch onto it. Isn't a perfectly white bit
stream
>> something you could never decode?
>
>Packed multimedia data looks very much like random bitstream, however
>you can clearly distinguish a valid decode from invalid.

If the undecoded bit stream doesn't look white there must be redundancy
that could be source coded out of it. If it does look perfectly white
there's nothing to latch onto until you decode it. Now, in some cases you
could decode every possible alignment of the data, and see which one makes
the most sense. That's only going to be possible when the comms channel is
tightly merged with the end end user activities, though. Even there it is
going to be a computational nightmare in most cases.

Have you found genuine practical applications for what you have done? How
about squeezing out every last scrap of excess bandwidth, so you can't even
blindly sync to the symbols? That sounds like a fun challenge. :-)

Steve

[Ravi Srikantiah]

On Jan 28, 10:16*pm, Vladimir Vassilevsky <[email protected]> wrote:
> In a couple of projects, I implemented frame synchronization based
> entirely on the structure of the data and FEC; i.e. without insertion of
> any preambles, sync markers or flags into the data stream. I even tried
> to optimize FEC with respect to frame synchronization. That idea worked
> nicely especially at low SNRs, although it can take a lot of computation.
>
> The concept seems kind of obvious. Just wondering if there is any
> relevant work in the literature; or if there are any practical
> communication systems which use that approach.
>
> Vladimir Vassilevsky
> DSP and Mixed Signal Design Consultanthttp://www.abvolt.com

The main drawback of this, I suppose, is the buffering. You'd need to
buffer sufficiently so that the FEC decisions can be fed back to the
synchronizer. With a block-based FEC, the latency can be large enough
to significantly eat into the inter-frame gap - enough to prevent
sharing of computational blocks between two back-to-back received
frames or for an rx-tx turnaround.

[Vladimir Vassilevsky]

steveu wrote:
>>
>>steveu wrote:
>>
>>>>In a couple of projects, I implemented frame synchronization based
>>>>entirely on the structure of the data and FEC;

> Have you found genuine practical applications for what you have done?

I had to do that because I work with VLF channels. The bandwidth and
power are VERY limited so every single bit and +1dB gain is important.

> How about squeezing out every last scrap of excess bandwidth, so you can't even
> blindly sync to the symbols? That sounds like a fun challenge. :-)

Yea, the non-power of 2 thing with variable constellation is in the plans.


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

[Vladimir Vassilevsky]

Ravi Srikantiah wrote:

> On Jan 28, 10:16 pm, Vladimir Vassilevsky <[email protected]> wrote:
>
>>In a couple of projects, I implemented frame synchronization based
>>entirely on the structure of the data and FEC; i.e. without insertion of
>>any preambles, sync markers or flags into the data stream. I even tried
>>to optimize FEC with respect to frame synchronization. That idea worked
>>nicely especially at low SNRs, although it can take a lot of computation.
>>
>>The concept seems kind of obvious. Just wondering if there is any
>>relevant work in the literature; or if there are any practical
>>communication systems which use that approach.
>
> The main drawback of this, I suppose, is the buffering. You'd need to
> buffer sufficiently so that the FEC decisions can be fed back to the
> synchronizer.
> With a block-based FEC, the latency can be large enough
> to significantly eat into the inter-frame gap - enough to prevent
> sharing of computational blocks between two back-to-back received
> frames or for an rx-tx turnaround.

This was intended for synchronous data streaming (as opposed to
packets); there is no additional latency since the decoder operates
separately from the synchronizer.

Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

[Vladimir Vassilevsky]

Malachy Moses wrote:

> Others have at least thought about it, for example, U.S. Patent
> 6,560,745, "Method of identifying boundary of markerless codeword"
> filed by the National Security Agency (NSA), issued in 2003.

Interesting. Thank you for the lead.

VLV

[[email protected]]

> The concept seems kind of obvious. Just wondering if there is any
> relevant work in the literature; or if there are any practical
> communication systems which use that approach.

Typically receivers of RBDS (Radio Data System) use a flywheel
mechanism that is a bit like what you are describing. If data
syndromes keep coming out zero (correct) it adds "momentum" to that
synchronization. I've had it work with some very noisy signals.

[Eric Jacobsen]

On 1/29/2010 6:59 AM, [email protected] wrote:
>> The concept seems kind of obvious. Just wondering if there is any
>> relevant work in the literature; or if there are any practical
>> communication systems which use that approach.
>
> Typically receivers of RBDS (Radio Data System) use a flywheel
> mechanism that is a bit like what you are describing. If data
> syndromes keep coming out zero (correct) it adds "momentum" to that
> synchronization. I've had it work with some very noisy signals.

That ought to work well for non-cyclic codes. For low-data-rate streams
like VLF the time taken to search through the possible locations is
probably doable, although it'd add latency, which may not be important.

--
Eric Jacobsen
Minister of Algorithms
Abineau Communications
http://www.abineau.com

[Manny]

On Jan 28, 5:16*pm, Vladimir Vassilevsky <[email protected]> wrote:
> In a couple of projects, I implemented frame synchronization based
> entirely on the structure of the data and FEC; i.e. without insertion of
> any preambles, sync markers or flags into the data stream. I even tried
> to optimize FEC with respect to frame synchronization. That idea worked
> nicely especially at low SNRs, although it can take a lot of computation.
>
> The concept seems kind of obvious. Just wondering if there is any
> relevant work in the literature; or if there are any practical
> communication systems which use that approach.
>
> Vladimir Vassilevsky
> DSP and Mixed Signal Design Consultanthttp://www.abvolt.com

Acoustic adaptive receivers use something vaguely related that goes by
hypothesis feedback, but this is done at the modulation level e.g. 4
hypotheses for QPSK. Not sure about the word _practical_ though
because it could be computationally expensive i.e. very much research
stuff.

-Momo