Homework Help is Here – Start Your Trial Now!
Math
Advanced Math
I Theorem 31.2 Correcting Capability of a Linear Code If the Hamming weight of a linear code is at least 2t + 1, then the code can correct any t or fewer errors. Alternatively, the same code can detect any 2t or fewer errors. PROOF We will use nearest-neighbor decoding; that is, for any received vector v, we will assume that the corresponding code word sent is a code word v' such that the Hamming distance d(v, v') is a minimum. (If there is more than one such v', we do not decode.) Now, suppose that a transmitted code word u is received as the vector v and that at most t er- rors have been made in transmission. Then, by the definition of distance between u and v, we have d(u, v) < t. If w is any code word other than u, then w – u is a nonzero code word. Thus, by assumption, 2t + 1< wt(w – u) = d(w, u) < d(w, v) + d(v, u) < d(w, v) + t, and it follows that t + 1< d(w, v). So, the code word closest to the re- ceived vector v is u, and therefore v is correctly decoded as u. To show that the code can detect 2t errors, we suppose that a trans- mitted code word u is received as the vector v and that at least one error, but no more than 2t errors, was made in transmission. Because only code words are transmitted, an error will be detected whenever a received word is not a code word. But v cannot be a code word, since d(v, u) < 2t, whereas we know that the minimum distance between distinct code words is at least 2t + 1.

I Theorem 31.2 Correcting Capability of a Linear Code If the Hamming weight of a linear code is at least 2t + 1, then the code can correct any t or fewer errors. Alternatively, the same code can detect any 2t or fewer errors. PROOF We will use nearest-neighbor decoding; that is, for any received vector v, we will assume that the corresponding code word sent is a code word v' such that the Hamming distance d(v, v') is a minimum. (If there is more than one such v', we do not decode.) Now, suppose that a transmitted code word u is received as the vector v and that at most t er- rors have been made in transmission. Then, by the definition of distance between u and v, we have d(u, v) < t. If w is any code word other than u, then w – u is a nonzero code word. Thus, by assumption, 2t + 1< wt(w – u) = d(w, u) < d(w, v) + d(v, u) < d(w, v) + t, and it follows that t + 1< d(w, v). So, the code word closest to the re- ceived vector v is u, and therefore v is correctly decoded as u. To show that the code can detect 2t errors, we suppose that a trans- mitted code word u is received as the vector v and that at least one error, but no more than 2t errors, was made in transmission. Because only code words are transmitted, an error will be detected whenever a received word is not a code word. But v cannot be a code word, since d(v, u) < 2t, whereas we know that the minimum distance between distinct code words is at least 2t + 1.

Advanced Engineering Mathematics
Advanced Engineering Mathematics
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
See similar textbooks
icon
Related questions
Question

. Prove that for nearest-neighbor decoding, the converse of Theorem
31.2 is true.

I Theorem 31.2 Correcting Capability of a Linear Code If the Hamming weight of a linear code is at least 2t + 1, then the code can correct any t or fewer errors. Alternatively, the same code can detect any 2t or fewer errors. PROOF We will use nearest-neighbor decoding; that is, for any received vector v, we will assume that the corresponding code word sent is a code word v' such that the Hamming distance d(v, v') is a minimum. (If there is more than one such v', we do not decode.) Now, suppose that a transmitted code word u is received as the vector v and that at most t er- rors have been made in transmission. Then, by the definition of distance between u and v, we have d(u, v) < t. If w is any code word other than u, then w – u is a nonzero code word. Thus, by assumption, 2t + 1< wt(w – u) = d(w, u) < d(w, v) + d(v, u) < d(w, v) + t, and it follows that t + 1< d(w, v). So, the code word closest to the re- ceived vector v is u, and therefore v is correctly decoded as u. To show that the code can detect 2t errors, we suppose that a trans- mitted code word u is received as the vector v and that at least one error, but no more than 2t errors, was made in transmission. Because only code words are transmitted, an error will be detected whenever a received word is not a code word. But v cannot be a code word, since d(v, u) < 2t, whereas we know that the minimum distance between distinct code words is at least 2t + 1.
Transcribed Image Text:I Theorem 31.2 Correcting Capability of a Linear Code If the Hamming weight of a linear code is at least 2t + 1, then the code can correct any t or fewer errors. Alternatively, the same code can detect any 2t or fewer errors. PROOF We will use nearest-neighbor decoding; that is, for any received vector v, we will assume that the corresponding code word sent is a code word v' such that the Hamming distance d(v, v') is a minimum. (If there is more than one such v', we do not decode.) Now, suppose that a transmitted code word u is received as the vector v and that at most t er- rors have been made in transmission. Then, by the definition of distance between u and v, we have d(u, v) < t. If w is any code word other than u, then w – u is a nonzero code word. Thus, by assumption, 2t + 1< wt(w – u) = d(w, u) < d(w, v) + d(v, u) < d(w, v) + t, and it follows that t + 1< d(w, v). So, the code word closest to the re- ceived vector v is u, and therefore v is correctly decoded as u. To show that the code can detect 2t errors, we suppose that a trans- mitted code word u is received as the vector v and that at least one error, but no more than 2t errors, was made in transmission. Because only code words are transmitted, an error will be detected whenever a received word is not a code word. But v cannot be a code word, since d(v, u) < 2t, whereas we know that the minimum distance between distinct code words is at least 2t + 1.
Expert Solution
steps

Step by step

Solved in 3 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Knowledge Booster
Linear Transformation
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, advanced-math and related others by exploring similar questions and additional content below.
Recommended textbooks for you
Advanced Engineering Mathematics
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Mathematics For Machine Technology
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
Basic Technical Mathematics
Basic Technical Mathematics
Advanced Math
ISBN:
9780134437705
Author:
Washington
Publisher:
PEARSON
Topology
Topology
Advanced Math
ISBN:
9780134689517
Author:
Munkres, James R.
Publisher:
Pearson,
SEE MORE TEXTBOOKS