Correcting an error

Logic Level 2

A noisy channel is known to flip bits with low frequency (so it can be safely assumed that double-bit errors will not occur). Alice has built the following partial encoding:

Letter Encoding
A 00000
B 00111
C 11001
D ?????

what value should Alice encode D as in order to achieve single-bit correction?


The answer is 11110.

Alexander Katz by Alexander Katz , 24, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

展豪 張
Mar 14, 2016

D must start with '11', otherwise we cannot distinguish AD (or BD).
Choose the inverse of C in the last three digit.
Answer is '11110'

2 Helpful 0 Interesting 1 Brilliant 0 Confused
Dylan Boland
Dec 7, 2019

If you look at how many bits each of the 5-bit sequences (each of which represent a letter) differ by, you'll get 3 - this is the ' hamming distance '. We want a new 5-bit sequence which will encode D, and it would be nice if it also differed from every other encoding by 3 bits - i.e. if it had the same hamming distance. After playing around with a few possibilities, you should find that 11110 is the solution to the problem! It differs from every other sequence by 3 bits, and so has the same hamming distance, meaning it'll work nicely with Alice's encoding scheme.

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...