Код Бергера

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

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

Однонаправленное обнаружение ошибок

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

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

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

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

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

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

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

Ссылки

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