{
  "id": "enwiki-001249382245",
  "slug": "plotkin-bound",
  "title": "Plotkin bound",
  "qid": "",
  "lead": "In the mathematics of coding theory, the Plotkin bound, named after Morris Plotkin, is a limit (or bound) on the maximum possible number of codewords in binary codes of given length n and given minimum distance d.",
  "body": "In the mathematics of coding theory, the Plotkin bound, named after Morris Plotkin, is a limit (or bound) on the maximum possible number of codewords in binary codes of given length n and given minimum distance d. d = \\min_{x,y \\in C, x \\neq y} d(x,y) where d(x,y) is the Hamming distance between x and y . The expression A_{2}(n,d) represents the maximum number of possible codewords in a binary code of length n and minimum distance&nbsp; d . The Plotkin bound places a limit on this expression. Theorem (Plotkin bound): i) If d is even and 2d > n , then A_{2}(n,d) \\leq 2 \\left\\lfloor\\frac{d}{2d-n}\\right\\rfloor. ii) If d is odd and 2d+1 > n , then A_{2}(n,d) \\leq 2 \\left\\lfloor\\frac{d+1}{2d+1-n}\\right\\rfloor. iii) If d is even, then A_{2}(2d,d) \\leq 4d. iv) If d is odd, then A_{2}(2d+1,d) \\leq 4d+4 where \\left\\lfloor ~ \\right\\rfloor denotes the floor function. == Proof of case i== Let d(x,y) be the Hamming distance of x and y , and M be the number of elements in C (thus, M is equal to A_{2}(n,d) ). The bound is proved by bounding the quantity \\sum_{(x,y) \\in C^2, x\\neq y} d(x,y) in two different ways. On the one hand, there are M choices for x and for each such choice, there are M-1 choices for y . Since by definition d(x,y) \\geq d for all x and y ( x\\neq y ), it follows that \\sum_{(x,y) \\in C^2, x\\neq y} d(x,y) \\geq M(M-1) d. On the other hand, let A be an M \\times n matrix whose rows are the elements of C . Let s_i be the number of zeros contained in the i 'th column of A . This means that the i 'th column contains M-s_i ones. Each choice of a zero and a one in the same column contributes exactly 2 (because d(x,y)=d(y,x) ) to the sum \\sum_{(x,y) \\in C, x \\neq y} d(x,y) and therefore \\sum_{(x,y) \\in C, x \\neq y} d(x,y) = \\sum_{i=1}^n 2s_i (M-s_i). The quantity on the right is maximized if and only if s_i = M/2 holds for all i (at this point of the proof we ignore the fact, that the s_i are integers), then \\sum_{(x,y) \\in C, x \\neq y} d(x,y) \\leq \\frac{1}{2} n M^2. Combining the upper and lower bounds for \\sum_{(x,y) \\in C, x \\neq y} d(x,y) that we have just derived, M(M-1) d \\leq \\frac{1}{2} n M^2 which given that 2d>n is equivalent to M \\leq \\frac{2d}{2d-n}. Since M is even, it follows that M \\leq 2 \\left\\lfloor \\frac{d}{2d-n} \\right\\rfloor. This completes the proof of the bound. ==See also== Diamond code Elias Bassalygo bound Gilbert–Varshamov bound Griesmer bound Hamming bound Johnson bound Singleton bound ==References==",
  "categories": [
    "20476821",
    "22899737",
    "23400961",
    "24043274",
    "24261919",
    "61225801"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1249382245",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1728053129.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001249382245",
    "type": "webpage",
    "title": "Plotkin bound",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/plotkin-bound",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          18
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          18
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001249382245",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1249382245",
    "note": "Immutable snapshot enwiki-001249382245"
  }
}