308
правок
Изменения
м
Нет описания правки
Легко понять, что если в одном бите из строки допущена ошибка, то с помощью дописанных <tex>k</tex> пар бит можно точно определить, какой именно бит ошибочный. Это объясняется тем, что каждая пара определяет один бит номера ошибочного бита в строке. Всего пар <tex>k</tex>, следовательно мы имеем <tex>k</tex> бит номера ошибочного бита, что вполне достаточно: общее число бит строки не превосходит <tex>2^k</tex>.
Теперь заметим, что в случае наличия ошибки в исходной строке, ровно один бит в каждой паре будет равен единице. Тогда нам достаточно хранить оставить только один бит из пары. Однако этого будет недостаточно, поскольку если только один добавленный бит не соответствует строке, при этом потребуется то нельзя понять, ошибка в нём или в строке. На этот случай можно добавить ещё один контрольный бит, отвечающий за местонахождение ошибки - в исходной или добавленной части, пусть он будет равен <tex>xor</tex>'у всех исходных битов (заметим, что в этом случае этот бит <tex>\oplus</tex> бит из пары = второй бит из пары, потому вторые биты в парах не нужны)строки.
== Определение и устранение ошибок в общем случае ==
Пусть <tex>\Sigma</tex> — исходный алфавит, <tex>C: \Sigma \to B^m</tex> — кодирование, <tex>B=(0,1)</tex>
