2.1.7. Задача о взвешивании монет

К настоящему времени уже введены основные понятия теории двоичных групповых кодов. Здесь разумно сделать паузу и закрепить эти понятия, рассмотрев ряд примеров. Классической задачей, непосредственно связанной с теорией кодов Хемминга, является так называемая задача о взвешивании монет.

Предположим, имеются восемь монет и весы без гирь и известно, что одна из этих монет является фальшивой. Фальшивая

монета по внешнему виду не отличается от настоящих, но имеет другую массу. Вам нужно найти фальшивую монету с помощью всего трех взвешиваний. Решение, которое легко найти, рассматривая проверочную матрицу -кода Хемминга, состоит в следующем.

Прежде всего занумеруем монеты числами от 1 до 8, и пусть первые 7 из них соответствуют столбцам матрицы Н для -кода Хемминга:

При первом взвешивании нужно взять монеты 1, 2, 3 и 5 (первая строка проверочной матрицы) и положить по две монеты на каждую чашу. При этом неважно, как распределить монеты по чашкам. Если весы находятся в равновесии, то фальшивой является одна из монет 4, 6, 7 или 8, а если они не находятся в равновесии, то фальшивой является одна из монет 1, 2, 3 или 5. Таким образом, после одного взвешивания удается исключить ровно половину возможностей. При втором взвешивании нужно взять монеты 1, 2, 4 и 6 и повторить эксперимент. Равновесие снова означает, что фальшивой является одна из монет 3, 5, 7 или 8, а отсутствие равновесия означает, что фальшивой является одна из монет 1, 2, 4 или 6 Результат этого взвешивания вместе с результатом предыдущего исключает еще две возможности. Например, если весы оба раза оказывались в равновесии, то фальшивой является либо монета 7, либо монета 8, поскольку только они не участвовали ни в одном взвешивании. Наконец, при последнем взвешивании следует взять монеты 1, 3, 4 и 7. Результат этого взвешивания однозначно определяет фальшивую монету. Процесс станет ясным, если рассмотреть дерево решений, показанное на рис. 2.1.

Из рис. 2.1 видно, что каждый возможный исход соответствует одному из столбцов матрицы Н, если интерпретировать равновесие как 0, а неравновесие как 1. Таким образом, множество результатов взвешиваний образует синдром и каждый синдром отвечает одной из возможных фальшивых монет. Единственное различие между задачей о взвешивании монет и задачей декодирования состоит в том, что при взвешивании заранее известно, что одна из монет является фальшивой, а при декодировании может оказаться, что все символы приняты верно. В любом случае мы пытаемся выделить одно из восьми возможных событий. Если бы существовал канал, в котором всегда появлялась одна ошибка, то можно было бы использовать код Хемминга длиной 8 и аналогия была бы полной.

Приведенный пример показывает очень важное свойство хороших кодов. Каждая проверка на четность организована таким

Рис. 2.1. Дерево решений для задачи о взвешивании монет: фальшивая монета

образом, чтобы получить максимальную информацию о положении ошибки. Таким образом, при первой проверке исключается половина возможных символов, при следующей — половина оставшихся и т. д. Большинство кодов, конечно, оказываются не столь эффективными; однако при построении кодов для различных специальных применений следует пытаться использовать этот принцип.