Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C++ Algorithms
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 Big Grin | :-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
Rate this: bad
good
Please Sign up or sign in to vote.

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.
  Permalink  
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 6

I just found (maybe) a solution, used in Bio-Computing, called "Tandem-Repeats"
 
But all Information I found were very Scientific Wink | ;) Only proofs and theorems but no implementation in Code...
 
Did anybody of you ever heard something about that or has some code?
  Permalink  
Rate this: bad
good
Please Sign up or sign in to vote.

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.
  Permalink  
Rate this: bad
good
Please Sign up or sign in to vote.

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?
  Permalink  
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 3

XOR the sequence with itself offset-ed form 0 to a maximum length, and seek for the longest sequence of 0s.
  Permalink  
Rate this: bad
good
Please Sign up or sign in to vote.

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 | :laugh:
But you'll not find any examples if you don't have a buzzword to search
  Permalink  
Rate this: bad
good
Please Sign up or sign in to vote.

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.
  Permalink  

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

  Print Answers RSS
0 Sergey Alexandrovich Kryukov 9,108
1 OriginalGriff 8,186
2 CPallini 2,613
3 Richard MacCutchan 2,231
4 Abhinav S 1,928


Advertise | Privacy | Mobile
Web04 | 2.8.140827.1 | Last Updated 27 Apr 2010
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100