find repetitions in data

Question

5.00/5 (3 votes)

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 22:44pm

ziopino70

Add a Solution

7 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Christian Graus · Answer 1 · 2010-04-25T22:46:00

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.

ziopino70 · Answer 2 · 2010-04-25T23:02:00

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

Emilio Garavaglia · Answer 3 · 2010-04-26T22:55:00

Solution 3

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

Posted 26-Apr-10 22:55pm

Emilio Garavaglia

#realJSOP · Answer 4 · 2010-04-26T23:36:00

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?

Posted 26-Apr-10 23:36pm

#realJSOP

ziopino70 · Answer 5 · 2010-04-27T03:57:00

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.

ziopino70 · Answer 6 · 2010-04-27T04:57:00

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?

Posted 27-Apr-10 4:57am

ziopino70

Henry Minute · Answer 7 · 2010-04-27T05:16:00

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.

Posted 27-Apr-10 5:16am

Henry Minute