Error Detection

  • Thread starter wubie
  • Start date
  • #1
wubie
[SOLVED] Error Detection

Hello,

I have a question about error detection.

Senario:

One person can see two coins. Each coin could be laying heads up or tails up. You cannot see the coins.

Question:

What is the minimum number of questions with a "yes" or "no" response need to determine the status of two coins (that is whether they lie heads up or tails up) if two lies are permitted. All questions are tabled before any answers are given, and no hypothetical questions are allowed.


I quickly came up with one way of determining the status of the two coins:

Ask this question FIVE times about the first coin:

"Is the first coin heads up?"

Then ask this question FIVE times about the second coin:

"Is the second coin tails up?"

By taking a majority decision, one could deduce the status of the two coins. But is there a better way?

In class we have been talking about Hamming Distances. But I can't figure out how I would set this question up with regards to Hamming Distance.


Any help is appreciated.
 

Answers and Replies

  • #2
wubie
Alright. I found out some key information that I was not aware of to solve this question.

The number of code words is equal to the number of outcomes.

The possible number of outcomes for two coins are:

Heads-Heads, Heads-Tails, Tails-Heads, Tails-Tails.

There are four outcomes and so I need four code words.


Also, if I need to correct two errors, then the Hamming Distance between codewords must be at least

2k + 1

Therefore since there are two lies, I must have a minimum Hamming Distance of 5 between codewords.

Now I know that using ten questions I could determine the status of both coins. So, once again, the question is, "Can I do better than ten questions?"



For more nfo. on Hamming Distances as well as the course that I am taking go to:

http://www.math.ualberta.ca/~tlewis/222_03f/scarlet2.pdf [Broken]

under the section Hamming Distance.


I am still working on this question so I will post my answer later.

Cheers everyone.
 
Last edited by a moderator:

Related Threads on Error Detection

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
16
Views
2K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
5
Views
10K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
1
Views
7K
  • Last Post
Replies
6
Views
3K
Top