Definition
Let be a q-ary code of length, i.e. a subset of . Let be the minimum distance of, i.e.
- ,
where is the Hamming distance between and .
Let be the set of all q-ary codes with length and minimum distance and let denote the set of codes in such that every element has exactly nonzero entries.
Denote by the number of elements in . Then, we define to be the largest size of a code with length and minimum distance :
Similarly, we define to be the largest size of a code in :
Theorem 1 (Johnson bound for ):
If ,
If ,
Theorem 2 (Johnson bound for ):
(i) If ,
(ii) If, then define the variable as follows. If is even, then define through the relation ; if is odd, define through the relation . Let . Then,
where is the floor function.
Remark: Plugging the bound of Theorem 2 into the bound of Theorem 1 produces a numerical upper bound on .
Read more about this topic: Johnson Bound
Famous quotes containing the word definition:
“It’s a rare parent who can see his or her child clearly and objectively. At a school board meeting I attended . . . the only definition of a gifted child on which everyone in the audience could agree was “mine.””
—Jane Adams (20th century)
“The very definition of the real becomes: that of which it is possible to give an equivalent reproduction.... The real is not only what can be reproduced, but that which is always already reproduced. The hyperreal.”
—Jean Baudrillard (b. 1929)
“Although there is no universal agreement as to a definition of life, its biological manifestations are generally considered to be organization, metabolism, growth, irritability, adaptation, and reproduction.”
—The Columbia Encyclopedia, Fifth Edition, the first sentence of the article on “life” (based on wording in the First Edition, 1935)