Fewest number of segments to identify a know symbol

[jdlinke]

This question started out as a thought experiment on a flight home from Japan a couple years ago. I've toyed with it since, but I don't know the best approach. I'm hoping someone can guide me in the right direction. I don't want the answer straight out, I'm mainly looking for a good way to approach the problem.

I may be making this more difficult than it needs to be.

Suppose you have an electronic seven-segment display, like the image I've attached. It's the sort you find on your radio, your alarm clock, etc. Given a *known set of symbols* (for instance, the digits 0-9), I want to figure out the smallest group of segments that must be monitored in order to determine the identity of all the symbols in the known set of symbols.

For instance, the digit '0' requires segments a, b, c, e, f, g. The digit '1' requires segments c, f.


As a way of abstracting this problem, I tried extending it to a simple binary table. For instance, this table lists all the combinations of the segments for each symbol (0-9) in a seven-segment display.

……………	.	Digits									
……………	.	0	1	2	3	4	5	6	7	8	9
-----------------------------------------------------------------------
Segments	a	1	0	1	1	0	1	1	1	1	1
……………	b	1	0	0	0	1	1	1	0	1	1
……………	c	1	1	1	1	1	0	0	1	1	1
……………	d	0	0	1	1	1	1	1	0	1	1
……………	e	1	0	1	0	0	0	1	0	1	0
……………	f	1	1	0	1	1	1	1	1	1	1
……………	g	1	0	1	1	0	1	1	0	1	0

From this you can see that we could remove segments 'f' and 'g', and still be able to determine the identity of each digit, because the column for that digit remains unique. But is this the smallest number of segments required? And how could that be proven, other than iterating through each possible combination?

Alternatively, if we remove segments 'e', 'f', and 'g', there is now ambiguity. Digits 2 & 3, 5 & 6, and 8 & 9 can no longer be identified uniquely.

I've tried breaking it down to simpler problems using just two or three segments (like the other attached image) and making up arbitrary sets of symbols for these, and trying to figure out how to determine the smallest group of segments required to determine the identity of all the symbols in the set, but I'm having no luck. I see patterns, but I don't have enough math education background to find identify the best tools to solve this problem.

It's kind of driving me nuts. Can anyone point me in the direction of which mathematical tool(s) would be appropriate for figuring something like this out?

 

[scurty]

This seems like a Coding Theory related question. I took the class 1.5 years ago so I don't remember everything, but is something like this a viable answer?

Generating Matrix G:
<br /> \left(<br /> \begin{array}{ccccc}<br /> 1 &amp; 0 &amp; 0 &amp; 1 &amp; 1 \\<br /> 0 &amp; 1 &amp; 0 &amp; 1 &amp; 0 <br /> \end{array}<br /> \right)<br />

Vectors V:

<br /> \left(<br /> \begin{array}{ccccc}<br /> 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\<br /> 1 &amp; 0 &amp; 0 &amp; 0 &amp; 1\\ <br /> 0 &amp; 1 &amp; 0 &amp; 1 &amp; 1\\ <br /> 1 &amp; 1 &amp; 0 &amp; 1 &amp; 0\\ <br /> 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0\\ <br /> 1 &amp; 0 &amp; 1 &amp; 1 &amp; 0\\ <br /> 0 &amp; 1 &amp; 1 &amp; 1 &amp; 1\\ <br /> 1 &amp; 1 &amp; 1 &amp; 0 &amp; 1\\ <br /> \end{array}<br /> \right)<br />

Basically, for v \in V, \quad v \cdot w = 0, \quad \forall w \in G if I remember correctly. I'll try to explain some more if you need more.