Какое минимальное количество контрольных бит должно передаваться вместе с 16-ю информационными для обеспечения восстановимости информации, если вероятность искажения составляет 1%?
Подставляя р = 0,01 в (5.7), находим Lmin » 1,081. При ki = 16 из (5.6.) получаем k = ki ∙ Lmin = 17,29. Следовательно, с учетом того, что количество контрольных бит выражается целым числом, kc ≥ k - ki = 2. Реальная избыточность согласно (5.6) составит L = 1,125.
Выражение (5.7) устанавливает границу избыточности, при которой возможно восстановление переданной информации, однако, не указывает, каким образом следует осуществить кодирование, чтобы ошибка могла быть локализована (т.е. определено, в каком бите она находится) и, естественно, устранена. Такой метод кодирования был предложен в 1948 г. Р. Хеммингом; построенные по этому методы коды получили название коды Хемминга [36].
Основная идея состоит в добавлении к информационным битам нескольких битов четности, каждый из которых контролирует определенные информационные биты. Если пронумеровать все передаваемые биты, начиная с 1 слева направо (стоит напомнить, что информационные биты нумеруются с 0 и справа налево), то контрольными (проверочными) оказываются биты, номера которых равны степеням числа 2, а все остальные являются информационными. Например, для 8-битного информационного кода контрольными окажутся биты с номерами 1, 2, 4 и 8:
Номера контролируемых битов для каждого проверочного приведены в табл. 5.1. В перечень контролируемых битов входит и тот, в котором располагается проверочный. При этом состояние проверочного бита устанавливается таким образом, чтобы суммарное количество единиц в контролируемых им битах было бы четным.
Таблица 5.1.
Легко усматривается принцип выделения контролируемых битов в табл. 5.1: для любого номера проверочного бита (п), начиная с него, п бит подряд оказываются проверяемыми, затем - группа п непроверяемых бит; далее происходит чередование групп.