Код Бергера

В телекоммуникациях код Бергера представляет собой однонаправленный код обнаружения ошибок, названный в честь его изобретателя, Дж. М. Бергера. Коды Бергера могут обнаруживать все однонаправленные ошибки. Однонаправленные ошибки - это ошибки, которые переводят только единицы в нули или только нули в единицы, например, в асимметричных каналах. Контрольные биты кодов Бергера вычисляются путем подсчета всех нулей в информационном слове и выражения этого числа в натуральном двоичном формате. Если информационное слово состоит из $n\; \{\backslash \; displaystyle\; n\}$бит, то для кода Бергера требуется $k\; =\; \lceil \; log\; 2\; \; (n\; +\; 1)\; \rceil \; \{\backslash \; displaystyle\; k\; =\; \backslash \; lceil\; \backslash \; log\; \_\; \{2\}\; (n\; +\; 1)\; \backslash \; rceil\}$«проверочные биты», дающие код Бергера длины k + n. (Другими словами, $k\; \{\backslash \; displaystyle\; k\}$проверочных битов достаточно для проверки $n\; =\; 2\; k\; -\; 1\; \{\backslash \; displaystyle\; n\; =\; 2\; ^\; \{k\}\; -1\; \}$информационные биты). Коды Бергера могут обнаруживать любое количество ошибок преобразования битов «один к нулю» до тех пор, пока в одном и том же кодовом слове не возникнет ошибок преобразования нуля в один. Точно так же коды Бергера могут обнаруживать любое количество ошибок переворота битов от нуля до единицы при условии, что в том же кодовом слове не возникает ошибок переворота один к нулю. Коды Бергера не могут исправить ни одной ошибки.

Как и все однонаправленные коды обнаружения ошибок, коды Бергера также могут использоваться в нечувствительных к задержке схемах.

Как указано выше, коды Бергера обнаруживают любое количество однонаправленных ошибок. Для данного кодового слова, если единственные ошибки, которые произошли, заключаются в том, что некоторые (или все) биты со значением 1 изменились на значение 0, то это преобразование будет обнаружено реализацией кода Бергера. Чтобы понять почему, рассмотрим три таких случая:

1. Некоторые биты единиц в информационной части кодового слова изменились на 0.
2. Некоторые биты единиц в контрольной (или избыточной) части кодовое слово изменилось на 0s.
3. Некоторые единицы битов как в информации, так и в проверочной части изменились на 0s.

Для случая 1 количество 0-значных битов в информационной части будет по определению ошибки увеличиваются. Следовательно, наш проверочный код Бергера будет ниже фактического 0-битного счетчика данных, и поэтому проверка не удастся.

Для случая 2 количество 0-значных битов в разделе информации осталось прежним, но значение контрольных данных изменилось. Поскольку мы знаем, что некоторые единицы превратились в нули, но никакие нули не превратились в единицы (именно так мы определили модель ошибки в этом случае), закодированное двоичное значение контрольных данных будет уменьшаться (например, с двоичного 1011 на 1010 или на 1001 или 0011). Поскольку информационные данные остались прежними, они имеют то же количество нулей, что и раньше, и это больше не будет соответствовать измененному контрольному значению.

Для случая 3, когда биты изменились как в разделе информации, так и в разделе проверки, обратите внимание, что количество нулей в разделе информации увеличилось, как описано для случая 1, и двоичное значение, сохраненное в контрольная часть снизилась, как описано для случая 2. Следовательно, нет шансов, что они в конечном итоге изменятся таким образом, чтобы стать другим допустимым кодовым словом.

Подобный анализ может быть выполнен, и он совершенно верен в случае, когда возникают единственные ошибки, когда некоторые 0-значные биты меняются на 1. Следовательно, если все ошибки, возникающие в конкретном кодовом слове все происходят в одном направлении, эти ошибки будут обнаружены. Для следующего передаваемого кодового слова (например) ошибки могут идти в противоположном направлении, и они все равно будут обнаруживаться, пока все они идут в одном направлении друг с другом.

В определенных ситуациях часто встречаются однонаправленные ошибки. Например, в флэш-памяти биты легче запрограммировать на 0, чем на 1.

• J. М. Бергер (март 1961 г.). «Примечание о коде обнаружения ошибок для асимметричных каналов». Информация и контроль. 4 (1): 68–73. doi : 10.1016 / S0019-9958 (61) 80037-5.
• Субхасиш Митра и Эдвард Дж. Маккласки, «Какую схему одновременного обнаружения ошибок выбрать? », Центр надежных вычислений, Стэнфордский университет, 2000. CiteSeer : 10.1.1.9.2021
• Том Верхофф (март 1988). «Нечувствительные к задержке коды - обзор] от» (PDF). Распределенных вычислений. 3 (1): 1–8. doi :10.1007/BF01788562.