3 ms·
Imagine taking a book off a shelf, flipping to a random page, then pointing at a random word on that page. Without any knowledge of the rest of the page or book
by TrueDuality 5y ago
Imagine taking a book off a shelf, flipping to a random page, then pointing at a random word on that page. Without any knowledge of the rest of the page or book you can tell whether that word is spelled correctly and exists in the dictionary. That is local testability.
With code words you need to be able to distinguish where the code word starts and stops and how long it is. For more complex code words not all bit combinations are valid just like not all combinations of letters are valid words.
The example given at the beginning of the article doesn't really go far enough. Yes if you repeat a bit 3 times, you can tell its corrupted if any of the three don't match (ignore the correction part of it because that is not part of local testability).
What the article doesn't cover in its example is that if you have a message that is a full gigabyte. You can skip to any part of that message (as long as you know the index you're at), find the beginning of the code word (it will have index % 3 == 0) and the next three bits and verify whether those have been corrupted or not as well.