Minimum-length encoding and error detection by code distance
[1/0%]LaTeX
Problem 1.4.2 from Глибичук А.А., Дайняк А.Б., Ильинский Д.Г., Купавский А.Б., Райгородский А.М., Скопенков А.Б., Чернов А.А. "Элементы дискретной математики в задачах" [ГДИ+16]More problems in Section 1.4 "Combinatorics of the Boolean Cube"
The 33 letters of the Russian alphabet are encoded by sequences of zeros and ones.
?
Origin: AI-translated from another node content of the same node
Generated from: Stated according to the original source
(1)
What is the least sequence length for which the encoding can be made unambiguous?
(2)
If an error in at most one digit is possible when a message is received, i.e., if the codes of different letters must differ in at least three digits, then 8 digits are not enough.
(3)
If an error in at most two digits is possible, then 10 digits are not enough.
(4)
Find the least number of digits sufficient for the encoding from part (2).
References
[ГДИ+16] Глибичук А.А., Дайняк А.Б., Ильинский Д.Г., Купавский А.Б., Райгородский А.М., Скопенков А.Б., Чернов А.А. Элементы дискретной математики в задачах. МЦНМО, 2016.