Пример 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: для любого номера проверочного бита (п), начиная с него, п бит подряд оказываются проверяемыми, затем - группа п непроверяемых бит; далее происходит чередование групп.

Глоссарий

Пример 7.4

Модели структурные и функциональные

Пример 4.11

Контрольные вопросы и задания

Вернуться в оглавление: Теоретические основы информатики