Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let's say I have a data stream of bits in which I'm attempting to detect a sixteen bit sync pattern (The pattern is FB28 or 1111 1011 0010 1000 in binary, if that matters)

If I allow a one bit error in the pattern to still be considered a match (e.g. EB28), what are the odds of a false positive?

I know that, if I confine the error to a single bit (say the high bit), the odds are 1 in 2^15 (or one in 32768), but if any bit can be in error, is it simply 32768 / 16? Or is it a combination/permutation problem?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

The number of pattern of 16 bits which differ by a single bit to the given pattern are 16 (one for every bit you can modify). So you have a false positive in $16/2^{16}$ cases.

share|improve this answer
    
Oy, that ugly. Once every 4096 bits. –  Robert Harvey Feb 19 '13 at 17:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.