EPROM仿真模式下清零位后仍唯一的最大字节值集合技术咨询

Great question! Let's break this down mathematically and practically for your DS2431 1-wire EEPROM use case.

First, let's model your problem in set theory terms—since each byte is just 8 bits, we can think of it as a subset of 8 possible positions where bits are set:

• Each valid ID byte represents a subset of the 8-bit positions (the positions where the bit is 1).
• Your core requirement translates to: no valid ID can be a subset of another valid ID (because modifying a byte in EPROM仿真 mode only lets you clear bits, turning a valid ID into a smaller subset of itself; you need this modified value to not be a valid ID).

This is exactly the definition of an antichain in the Boolean lattice of 8-bit subsets, and we have a classic theorem that answers your question directly:

Sperner's Theorem #

Sperner's theorem tells us that for an n-element set (here, n=8 bits), the largest possible antichain is formed by all subsets of size ⌊n/2⌋ (or ⌈n/2⌉, which is identical when n is even).

For n=8:

• ⌊8/2⌋ = 4, so the largest antichain is all 8-bit bytes with a popcount (number of 1 bits) of 4.
• The size of this set is the binomial coefficient C(8,4) = 70—exactly the set you initially considered!

Why a larger set isn't possible #

You might wonder if mixing subsets of different sizes (e.g., some popcount=3 and some popcount=5) could yield a bigger valid set. Here's why that won't work:

• The binomial coefficients for 8 bits peak at popcount=4 (70 elements), with popcount=3 and 5 each only giving 56 elements.
• Any antichain mixing different popcounts can't exceed the size of the largest single-popcount antichain. For example, if you pick a popcount=5 byte, it contains 10 different popcount=3 subsets—you'd have to exclude all those 3-popcount bytes to maintain the antichain property, which would reduce the total size below 70.

Practical fit for your DS2431 #

Your initial choice is perfect for your use case:

• Every valid ID has exactly 4 bits set.
• Clearing any bit (or multiple bits) reduces the popcount to 3 or lower, which isn't in your valid set—so you guarantee no modified version of a valid ID can be another valid ID.

No larger set can satisfy your requirement, since Sperner's theorem proves 70 is the maximum size of such an antichain for 8-bit values.

内容的提问来源于stack exchange，提问作者spiff42