6

Say we have K binary numbers (each of same length). We need to find minimum of number of bits needed (need not be continuous) to uniquely identify these K binary numbers. For example 100, 110 can be distinguished by 1 bit (at second position). 111, 110, 101 need 2 bits to be distinguished.

NathanOliver
  • 171,901
  • 28
  • 288
  • 402
Papudeet Berandhi
  • 103
  • 6

1 Answers1

3

We can see those binaries as a set of linear equations. So, for example , if we have these binary : 1111, 1100, 1001, we can represent them as follow:

x1 + x2 + x3 + x4 = y1
x1 + x2 + 0  + 0  = y2
x1 + 0  + 0  + x4 = y3

From here, we realize that, we can use Gaussian elimination to reduce those equations to eliminate extra variables (in above example, it is x1). The result of the reduction will be set of K distinct variables, and we remove one extra variable to obtain the result of the original question.

Pham Trung
  • 11,204
  • 2
  • 24
  • 43
  • This will give all the bits that are different. For example in your example this only eliminates one variable where as minimum needed to distinguish is 2. – Papudeet Berandhi Oct 22 '16 at 06:24
  • @PapudeetBerandhi I have mentioned in my answer, you can always remove one more bit from the Gaussian elimination result to get the final answer. – Pham Trung Oct 22 '16 at 11:00
  • @PapudeetBerandhi , Pham, I think misunderstood the question - could you please help me understand how only two bits distinguish `[1111, 1100, 1001]` (and which ones)? Also, how would it be different, in terms of Gaussian elimination as well as the distinguishing bits, if we added `1000` to that example? – גלעד ברקן Oct 22 '16 at 13:11
  • @PhamTrung, consider [1111, 1100, 1001] now these three numbers can be distinguished by bits located at positions 3 and 4 i.e: the last two bits. For [1111, 1100, 1001, 1000] we need three bits to distinguish (the last three). Gaussian eilimation just remove extra bits (like the bit 1 at first position in both the examples) but it does not give us the least number of bits needed.. – Papudeet Berandhi Oct 22 '16 at 14:16
  • @גלעדברקן In order to solve an K-equation system, you can only have K unique variables in the system, otherwise, it is unsolvable. The elimination help you to solve the system, thus, archive the target, as it reduces all equations to a K variables system, with the last row only contains one variable (which also the one you can remove). You can try Gaussian elimination [here](http://matrix.reshish.com/gauss-jordanElimination.php) and verify yourself – Pham Trung Oct 22 '16 at 14:54
  • @PapudeetBerandhi don't you need bits 2 and 4 to distinguish between `1100` and `1001`? – גלעד ברקן Oct 22 '16 at 15:45
  • 1100 and 1001 can be distinguished by bits of following combinations 1234, 123,12,2,4,23,24. Any of these combinations can be used to distingish 1100 and 1001 – Papudeet Berandhi Oct 22 '16 at 16:10
  • @Pham nice answer! – גלעד ברקן Oct 22 '16 at 16:22
  • @PapudeetBerandhi oh, I originally thought you meant which bits are needed to show the complete difference between two numbers, so for 1100 and 1001 there are two bits. But what I understand from you now is that you are looking for *any* one bit that's different, which is why you can accept bit 2 or 4 by itself to "distinguish" between the two numbers. – גלעד ברקן Oct 22 '16 at 16:27
  • Exactly, I need the minimum number of bits with which we can show the difference. Any idea? – Papudeet Berandhi Oct 23 '16 at 01:48