Error-correcting codes
Linear block codes: length, dimension, minimum distance and rate, detection and correction power, encoding with a generator matrix, syndrome decoding and the families in use.
- 28 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
A few cards from the deck
Linear code: what is it?
Show the answer
A set of binary words of length n, closed under exclusive or: the sum of two code words is again a code word.
An [n, k] code has 2^k words. Linearity allows encoding and decoding with matrix products, and its minimum distance is the smallest weight of a non-zero word.
A linear code contains the four words
000000,101101,011011and110110. What is its minimum distance?4236
Show the answer
4For a linear code, the minimum distance is the smallest weight of a non-zero word. Each of the three non-zero words has four 1s, hence 4. The zero word is not counted.
A code of minimum distance d detects up to … errors and corrects up to ….
Show the answer
A code of minimum distance d detects up to d − 1 errors and corrects up to ⌊(d − 1)/2⌋.
To correct, the received word must stay closer to the right word than to any other: errors must stay below half the distance.
Minimum distance: what is it?
Show the answer
The smallest number of positions in which two distinct code words differ.
It sets the powers of the code: it detects up to d − 1 errors and corrects up to ⌊(d − 1)/2⌋.