Singleton bound

The singleton bound denotes an upper bound for the minimum distance d of a block code of length n with k information words of length on a single alphabet. It reads:

  • Assumption: Alphabet
  • Number of possible information words: | I | =
  • Number of code words: | C | = | I | =
  • Minimum distance: d

You now sweeps in the codewords in each case the last ( d -1) of n points, so have the rest of the code words to each other is still the least Hamming distance 1 (for d deletions, this would no longer be guaranteed ). This is still all codewords different, so

Therefore, must be producible words, the number of the length n- (d- 1). If this equation around, the result is the Singleton bound

Codes that meet the Singleton bound with equality is also called MDS codes.

Singleton bound#MDS codes
731791
de