Количество контрольных бит. Пример 5.3

Какое малое количество контрольных бит должно передаваться совместно с 16-ю информационными для обеспечения восстановления информации, если возможность преломления составляет 1%?

Подставляя р = 0,01 в (5.7), находим L_min » 1,081. При k_i = 16 из (5.6.) получаем k = k_i ∙ L_min = 17,29. Как следует, с учетом того, что количество контрольных бит выражается целым числом, k_c ≥ k — k_i = 2. Настоящая избыточность согласно (5.6) составит L = 1,125.

Выражение (5.7) устанавливает границу избыточности, при которой может быть восстановление переданной информации, но, не показывает, каким образом следует выполнить кодирование, чтоб ошибка могла быть локализована (т.е. определено, в каком бите она находится) и, естественно, устранена. Таковой способ кодировки был предложен в 1948 г. Р. Хеммингом; построенные по этому способы коды получили заглавие коды Хемминга [36].

Основная мысль состоит в добавлении к информационным битам нескольких битов четности, любой из которых держит под контролем определенные информационные биты. Если пронумеровать все передаваемые биты, начиная с 1 слева вправо (стоит напомнить, что информационные биты нумеруются с 0 и справа влево), то контрольными (проверочными) оказываются биты, номера которых равны степеням числа 2, а все другие являются информационными. К примеру, для 8-битного информационного кода контрольными окажутся биты с номерами 1, 2, 4 и 8:

Номера контролируемых битов для каждого проверочного приведены в табл. 5.1. В список контролируемых битов заходит и тот, в каком размещается проверочный. При всем этом состояние проверочного бита устанавливается таким образом, чтоб суммарное количество единиц в контролируемых им битах было бы четным.

Таблица 5.1.

Просто усматривается принцип выделения контролируемых битов в табл. 5.1: для хоть какого номера проверочного бита (п), начиная с него, п бит по порядку оказываются проверяемыми, потом — группа п не проверяемых бит; дальше происходит чередование групп.