12,695,049 members (31,355 online)
Rate this:
See more:
Hi,
I have to detect repetitions in signal data (carrier-modulated digital signal) which looks similar that
`10101010 0001010000001010 0001010000001010 0001010000001010 0101010000000000`
(spaces just for human-readability :-D )
As you can see, the
`0001010000001010 `
pattern repeats.

Can you please give me some hints for algorithms or any ideas to detect that repetition.
Posted 25-Apr-10 23:44pm

Rate this:

## Solution 7

I do not know how to answer your question directly but it occurs to me that in compression techniques, particularly those that use Huffman Coding, a search is made for the most commonly repeated data to get the best compression.

Might there be something transferable to your problem there.
Rate this:

## Solution 6

I just found (maybe) a solution, used in Bio-Computing, called "Tandem-Repeats"

But all Information I found were very Scientific ;) Only proofs and theorems but no implementation in Code...

Did anybody of you ever heard something about that or has some code?
Rate this:

## Solution 5

I'm not intressted in the values - just in the repeating sub-string

Its a Signal with Pre-Signal bits, the Main-Signal (maybe with repetitions) and an Post-Signal

pre1pre2pre3main1main2main1main2main1main2main1main2post1post2
should be converted to
pre1pre2pre3main1main2[4times]post1post2

but the recorded signal also can look like this
pre1pre2pre3main1main2main3main4post1
or this
pre1main1main2main3 or pre1main1main2main3main1main2main3
or even this
main1main2

( the main problem is, that I don't know where the Pre-Signal ends and the main Signal begins. But its no problem, if some bits belonging to main-Signal later would be in the Pre-Signal field or vice versa.
Rate this:

## Solution 4

Are you looking for just one specific repeating value, or all values that repeat? Are you interested in counting the repetitions, or do you just want to know that a given value repeats?
Rate this:

## Solution 3

XOR the sequence with itself offset-ed form 0 to a maximum length, and seek for the longest sequence of 0s.
Rate this:

## Solution 2

In the second step 0000 will be 2 times of 00 - but in first step I want to find the longest possible stream.
(But thats the same problem again, just with a subset of the input data...)

You're right, that will bei the easiest method - but it also will be veeery inefficient.
If you find a repetition of 00 for example, in the next step you may increase your counter by 2...

I think, I'm not the first who have such or a similar problem, certainly some intelligent people thought long about that to find an efficient way.... :laugh:
But you'll not find any examples if you don't have a buzzword to search
Rate this:

## Solution 1

I guess you need to define how big a repetion counts. Does 0000 count as a repetition of 00 ? Apart from that, it seems to me you need to walk your data, and at each point from min length to max length, walk the whole data looking for a repeat. Then move your starting point forward by one and repeat again.

If the data is coming in a steady stream, you could write some code to store the sequences you're looking for and keep track of if they repeat as you go. But you'd need to be storing the new sequences for future matches also.

Top Experts
Last 24hrsThis month
 OriginalGriff 495 Richard Deeming 170 Peter Leow 120 ppolymorphe 93 Jochen Arndt 80
 OriginalGriff 3,403 Peter Leow 2,145 Mika Wendelius 1,743 ppolymorphe 1,529 Jochen Arndt 1,324