Bounding A ( n , d ) = <mo movablelimits="true" form="prefix">max <mo fence="fals

osmane5e 2022-05-24 Answered
Bounding A ( n , d ) = max { M | exists a code with parameters n,M,d}
I would like to prove that this lower bound of A ( n , d ) = max { M | exists a code with parameters n,M,d} (where n is the length of the block code, M the number of words of the code, and d, the minimal distance of the code), holds:
2 n i = 0 d 1 ( n i ) A ( n , d )
For trying to see this, I have tried to connect this inequality with the cardinal of the ball of radius d 1, that is i = 0 d 1 ( n i ) 2 i , so for sure, that quantity is less than 2 n i = 0 d 1 ( n i ) . But I don't see if this is or not helping me at all... I would appreciate some guidance, help, hint,... Thanks!
You can still ask an expert for help

Want to know more about Discrete math?

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

Scarlet Reid
Answered 2022-05-25 Author has 8 answers
Step 1
You are nearly there! Note that the sphere of Hamming radius t has i = 0 d 1 ( n i ) vectors in it, not i = 0 d 1 ( n i ) 2 i vectors as you state.
Suppose that there are spheres of Hamming radius d 1 centered at the M codewords in a (n, M, d) code. Some of these spheres might be overlapping (i.e., not disjoint) but never mind that. The total volume occupied by these M spheres (ignoring the overlap) is M i = 0 d 1 ( n i ) . Now, if it so happens (1) M i = 0 d 1 ( n i ) < 2 n ,
then there is at least one vector in the binary n-space that is, by construction, at distance d or more from all the M codewords that we started with. So, we can include this vector in our code to create a ( n , M + 1 , d ) code. Lather, rinse, and repeat. We now have a ( n , M + 1 , d ) code for which we can test whether (2) ( M + 1 ) i = 0 d 1 ( n i ) < 2 n holds or not. If (2) holds, we can add another codeword to construct a ( n , M + 2 , d ) code, and repeat the whole process again.
Step 2
We stop when we reach a point where we have a (n, M′, d) code for which the inequality reverses:
M i = 0 d 1 ( n i ) 2 n
and we can no longer apply the above argument. We could try to see if more sophisticated thinking and reasoning about the overlap between spheres that we totally ignored might improve the result, but we won't: many people have already tried without much success. But, we have shown that there exists a (n, M′, d) code such that M i = 0 d 1 ( n i ) 2 n M 2 n i = 0 d 1 ( n i ) .
It follows that A ( n , d ) 2 n i = 0 d 1 ( n i ) which is the result you are trying to prove.
Not exactly what you’re looking for?
Ask My Question

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Relevant Questions

asked 2021-08-15
How many elements are in the set { 0, { { 0 } }?
asked 2021-07-28

Let A, B, and C be sets. Show that (AB)C=(AC)(BC)
image

asked 2021-08-02
Suppose that A is the set of sophomores at your school and B is the set of students in discrete mathematics at your school. Express each of these sets in terms of A and B.
a) the set of sophomores taking discrete mathematics in your school
b) the set of sophomores at your school who are not taking discrete mathematics
c) the set of students at your school who either are sophomores or are taking discrete mathematics
Use these symbols:
asked 2021-08-18
Discrete Mathematics Basics
1) Determine whether the relation R on the set of all Web pages is reflexive, symmetric, antisymmetric, and/or transitive, where (a,b)R if and only if
I) everyone who has visited Web page a has also visited Web page b.
II) there are no common links found on both Web page a and Web page b.
III) there is at least one common link on Web page a and Web page b.
asked 2022-06-13
How can I prove that a function is surjective?
I understood by scrolling through the old posts, that if i have a function like this:
f : R { 2 } R { 5 } f ( x ) = 5 x + 1 x 2
If it is given to me something like this: f : N × N N f ( ( n , m ) ) = 2 n 1 ( 2 m 1 ), how can i prove that is surjective? The fact that i have 2 variable is confusing me. Thanks, I hope the question is well asked.
asked 2021-08-03
Give the full and correct answer for define discrete math?
asked 2022-05-23
Solution of linear congruence system
Solve { 2 x 1   ( mod 5 ) ( 5 x + 2 ) 2 ( mod 18 )
Now I have read about the Chinese Remainder Theorem, which is particularily helpful in solving systems of linear congruence, but in this notice that the moduli are not relatively prime (pairwise). So, I cannot apply the theorem. In fact this leads me to a general question: If we are given as system:
a 1 x b 1 ( mod n 1 ) a 2 x b 2 ( mod n 2 ) a 3 x b 3 ( mod n 3 ) a 4 x b 4 ( mod n 4 ) . . . a r x b r ( mod n r )
where the moduli are not pairwise relatively prime. How do we go about solving this system and what are the conditions that determine the solvability of the system.

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question