Контрольная сумма Флетчера

Контрольная сумма Флетчера (переводимая как «контрольная сумма Флетчера», также контрольная сумма Флетчера или алгоритм Флетчера ) - это метод обнаружения ошибок в форме контрольной суммы, введенный в 1982 году Джоном Г. Флетчером (1934–2012) . Метод может использоваться для обнаружения ошибок, например, при передаче цифровых данных . Он основан на том, что отдельные биты сообщения не только складываются, но и взвешиваются в зависимости от их положения. Таким образом, алгоритм представляет собой компромисс между более медленной, но более чувствительной проверкой циклическим избыточным кодом (CRC) и подверженными ошибкам процедурами, такими как простая проверка контрольной суммы или вертикальной избыточности . Контрольная сумма Флетчера используется в различных сетевых протоколах и файловых системах.

Алгоритм

Сообщение, передаваемое в двоичном формате , делится на части по длине , каждый бит образует блок . Последний блок заполняется на время выполнения алгоритма, и каждый блок интерпретируется как целое число без знака . Пусть количество блоков будет . Контрольное значение состоит из двух разных сумм: первая ( ) суммирует все блоки шаг за шагом, вторая ( ) представляет собой сумму всех промежуточных результатов первой суммы. Первый блок вводится несколько раз , последний блок - только один раз. Если биты инвертированы или два блока с разными значениями меняются местами из-за помех во время передачи, тестовое значение обычно изменяется: обнаружена ошибка. ${\ displaystyle K}$ ${\ displaystyle K}$ ${\ displaystyle {\ text {length}}}$ ${\ displaystyle {\ text {sum}} _ {1}}$ ${\ displaystyle {\ text {sum}} _ {2}}$ ${\ displaystyle {\ text {length}}}$ ${\ displaystyle {\ text {sum}} _ {2}}$

Поскольку тестовое значение должно быть передано в фиксированном количестве бит (как правило ) независимо от длины сообщения , обе суммы вычисляются по модулю последнего и затем интегрируются в сообщение. Обычно выбирается или . Последнее предпочтительнее, несмотря на несколько более сложный расчет, потому что он сопоставим по размеру, в отличие от, но не через 2 - основу двоичной системы - делимой . Для результата не имеет значения, используется ли операция по модулю после каждого сложения или в конце. Во избежание переполнения это происходит в одной реализации во время расчета. ${\ Displaystyle 2 \ cdot K}$ ${\ displaystyle M}$ ${\ Displaystyle M = 2 ^ {K}}$ ${\ Displaystyle M = 2 ^ {K} -1}$ ${\ displaystyle 2 ^ {K} -1}$ ${\ displaystyle 2 ^ {K}}$

Количество возможных тестовых значений из контрольной суммы Флетчера составляет . Если предположить, что сообщение достаточно длинное, вероятность того, что поврежденное сообщение будет иметь такое же значение проверки, уменьшается . В принципе, можно выбрать любое натуральное число ; соответственно алгоритм будет называться Fletcher- . Флетчер-16 и Флетчер-32 являются общими, в некоторых случаях также Флетчер-8. ${\ displaystyle M ^ {2}}$ ${\ displaystyle K}$ ${\ displaystyle K}$ ${\ Displaystyle 2 \ cdot K}$

Пример расчета

Если сообщение «Википедия» передается в двоичном коде ASCII , расчет, показанный в таблице, выполняется для Fletcher-16 . Если промежуточный результат в сумме больше или равен 255, используется модуль по модулю, показанный здесь как . ${\ displaystyle M = 255}$ ${\ Displaystyle \ Equiv}$

сообщение	W.	я	k	я	п	е	d	я	а	Результат
двоичное представление	01010111	01101001	01101011	01101001	01110000	01100101	01100100	01101001	01100001
десятичное значение	87	105	107	105	112	101	100	105	97
${\ displaystyle {\ text {sum}} _ {1}}$	87	192	299 44 ${\ Displaystyle \ Equiv}$	149	261 6 ${\ Displaystyle \ Equiv}$	107	207	312 57 ${\ Displaystyle \ Equiv}$	154	154
${\ displaystyle {\ text {sum}} _ {2}}$	87	279 24 ${\ Displaystyle \ Equiv}$	68	217	223	330 75 ${\ Displaystyle \ Equiv}$	282 27 ${\ Displaystyle \ Equiv}$	84	238	238

Псевдокод

Ниже приведен псевдокод для Fletcher-16 без какой-либо оптимизации. Обе суммы последовательно возвращаются в качестве тестового значения. ${\ displaystyle M = 255}$

Fletcher_16 (data)
Input: Array data von 8-Bit-Integern
Output: 16-Bit-Prüfsumme zu data

sum1 := 0
sum2 := 0
for i := 0 to length (data) do
    sum1 := (sum1 + data[i]) modulo 255
    sum2 := (sum2 + sum1) modulo 255
endfor
checksum := sum1 gefolgt von sum2
return checksum

варианты

В варианте, который ближе к исходному алгоритму Флетчера, к концу сообщения добавляются два тестовых блока длины , которые выбираются так, что обе суммы тестового значения для нового расширенного сообщения равны нулю. Для этого сначала рассчитываются две суммы и, как и раньше. Затем значение присваивается первому и второму тестовым блокам . Вскоре после публикации Флетчера Бетти Зальцберг показала, что положение двух последовательных тестовых блоков может быть выбрано по желанию в сообщении без ухудшения свойств теста. Если блоки должны быть на месте или , их значение должно быть выбрано как и , в каждом случае по модулю . Количество блоков соответствует исходному сообщению. На самом деле, два блока может быть свободно выбираемыми позиции , и до тех пор , как суммы и взаимно просты . ${\ displaystyle K}$ ${\ displaystyle {\ text {sum}} _ {1}}$ ${\ displaystyle {\ text {sum}} _ {2}}$ ${\ displaystyle - {\ text {sum}} _ {1} - {\ text {sum}} _ {2} {\ pmod {M}}}$ ${\ displaystyle {\ text {sum}} _ {2}}$ ${\ displaystyle n}$ ${\ displaystyle n + 1}$ ${\ displaystyle ({\ text {length}} - n) \ cdot {\ text {sum}} _ {1} - {\ text {sum}} _ {2}}$ ${\ displaystyle ({\ text {length}} - (n-1)) \ cdot (- {\ text {sum}} _ {1}) + {\ text {sum}} _ {2}}$ ${\ displaystyle M}$ ${\ displaystyle {\ text {length}}}$ ${\ displaystyle i}$ ${\ displaystyle j}$ ${\ displaystyle | ij |}$ ${\ displaystyle M}$

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

оптимизация

Если суммы сохраняются в более чем битах, операцию по модулю не нужно выполнять после каждого сложения, а только тогда, когда переменная угрожает переполнением. Предполагается наихудший случай , то есть сообщение, в котором каждый блок имеет максимально возможное значение для определения верхней границы количества добавлений без переполнения. Если обе суммы имеют одинаковый тип данных , это делается в первую очередь . При реализации Fletcher-16 с использованием и и беззнаковых 16-разрядных целых чисел . ${\ displaystyle K}$ ${\ displaystyle B_ {u}}$ ${\ displaystyle {\ text {sum}} _ {2}}$ ${\ displaystyle K = 8}$ ${\ displaystyle M = 255}$ ${\ displaystyle B_ {u} = 21}$

Кроме того, операцию по модулю можно заменить поразрядными операторами . Если вместо (отмеченного в языке программирования C ) достаточно , можно использовать арифметику дополнения до единицы , в которой добавление переноса (сквозного переноса), требуемого в этой арифметике, дает соответствующий результат. Однако современное оборудование использует почти исключительно арифметику с дополнением до двух ; добавление переноса в этом случае может имитироваться при условии, что используемый тип данных может вместить более чем биты. В литературе по контрольным суммам в целом, а также в литературе Флетчера, соответственно часто упоминаются версии с дополнительными единицами и двумя. ${\ Displaystyle M = 2 ^ {K}}$ x & (M-1)x % M ${\ Displaystyle M = 2 ^ {K} -1}$ (x & (M-1)) + (x >> K) ${\ displaystyle K}$ ${\ Displaystyle M = 2 ^ {K} -1}$ ${\ Displaystyle M = 2 ^ {K}}$

Контрольную сумму Флетчера можно распараллелить, а также векторизовать . Алгоритм также можно ускорить с помощью общих методов оптимизации , в частности, разворачивания цикла .

сказка

Джон Флетчер разработал алгоритм в Ливерморской национальной лаборатории Лоуренса в конце 1970-х годов . В январе 1982 года Общество связи IEEE опубликовало статью Флетчера о контрольной сумме и ее свойствах в документе IEEE Transactions on Communications . Этим он оправдывает свою разработку арифметической контрольной суммы тем фактом, что компьютеры предназначены для арифметических операций, а не для полиномиального деления , как того требует циклический контроль избыточности. Флетчер описал значение теста не как комбинацию двух, а любого количества сумм, при этом первая вычисляется как, а каждая дополнительная сумма складывает промежуточные результаты предыдущей. Однако использование более двух сумм не улучшает алгоритм в достаточной степени, чтобы гарантировать замедление. ${\ displaystyle {\ text {sum}} _ {1}}$

Адаптированные варианты алгоритма Флетчера используются, среди прочего, на четвертом уровне (транспортном) стандарта сетевого протокола ISO и в протоколе IS-IS . Дж. Цвейг и К. Партридж в 1990 г. предложили расширить протокол TCP , чтобы можно было использовать контрольную сумму Флетчера. Это пристройка имеет статус Исторического с 2011 года . Контрольная сумма используется как в файловой системе ZFS, представленной в 2006 году, так и в файловой системе Apple, представленной в 2016 году .

В 1995 году от Марка Адлера до Адлера-32 - это вариант предыдущего Флетчера-32, ожидается по модулю 65 521 (самый большой в простом числе меньше 2 ¹⁶ ).

Свойства и сравнение с другими методами

Если количество байтов в контрольном значении одинаково, контрольная сумма Флетчера подвергается хорошо реализованной циклической избыточной проверке (CRC) при обнаружении ошибок. Расчет может начаться до того, как сообщение будет завершено, потому что нет прямых зависимостей . Если отдельные блоки изменены после того, как контрольная сумма уже вычислена, ее можно обновить без доступа к неизмененным блокам. ${\ displaystyle {\ text {length}}}$

Следующие свойства всегда относятся к алгоритму . Контрольная сумма Флетчера обнаруживает все ошибки связки вплоть до длины ; она подвержена пакетным ошибкам, которые инвертируют блок, состоящий только из единиц, в один из одних только нулей или наоборот, потому что по модулю эти два блока эквивалентны. Если этот особый тип ошибки не рассматривается, распознаются все ошибки пакета до длины . Для сообщений до длины бит, причем способ имеет расстояние Хэмминга от , для более длинных сообщений . Fletcher-16 больше не распознает все двухбитовые ошибки из сообщения длиной 2056 бит, в то время как расстояние между двумя ошибками до 65 535 бит является достаточным для подходящего CRC с контрольным значением такой же длины. Здесь выявляется слабость реализации Fletcher-16 , поскольку расстояние здесь должно быть меньше или равно 16 битам. ${\ Displaystyle M = 2 ^ {K} -1}$ ${\ displaystyle K}$ ${\ displaystyle 2 ^ {K} -1}$ ${\ Displaystyle 2 \ cdot K}$ ${\ Displaystyle К \ cdot M = K \ cdot (2 ^ {K} -1)}$ ${\ displaystyle h = 3}$ ${\ displaystyle h = 2}$ ${\ displaystyle M = 256}$

Контрольная сумма Флетчера не распознает ложные нули, прикрепленные к сообщению, поскольку это означает, что суммы больше не меняются. Этого можно избежать, заранее зная длину сообщения или проинформировав получателя в нем.

Хотя с Adler-32 занятие простого числа распределяет возможные тестовые значения лучше, все меньше из них в целом, так что более сложные вычисления почти всегда испытывает хуже , чем Флетчер-32. ${\ displaystyle M}$

Таким образом, при одинаковом количестве битов в контрольном значении контрольная сумма Флетчера превосходит простые алгоритмы, такие как проверка с вертикальным избыточным кодом , простая сумма или контрольная сумма XOR и контрольная сумма Адлера. Если CRC может быть реализован, это должно быть предпочтительным.

литература

Джон Г. Флетчер: Арифметическая контрольная сумма для последовательных передач . В: IEEE Transactions on Communications . Том 30, выпуск 1, 1982 г., DOI: 10.1109 / TCOM.1982.1095369 , стр. 247-252.
Анастасия Накассис: Алгоритм обнаружения ошибок Флетчера: как его эффективно реализовать и как избежать наиболее распространенных ошибок. В: Обзор компьютерных коммуникаций . Том 18, выпуск 5, 1988 г., DOI: 10.1145 / 53644.53648 , стр. 63-88.
Джон Кодис: Контрольная сумма Флетчера: исправление ошибок за небольшую плату . В: Dr. Журнал Добба . Том 17, Выпуск 5, 1992 г., стр.32.
Тереза К. Максино, Филип Дж. Купман: Эффективность контрольных сумм для встроенных сетей управления . В: Транзакции IEEE о надежных и безопасных вычислениях . Том 6, выпуск 1, 2009 г., DOI: 10.1109 / TDSC.2007.70216 , особенно глава 3.4 (PDF; 676 kB).

веб ссылки

Дж. Цвейг, К. Партридж: Параметры альтернативной контрольной суммы TCP . RFC 1146, 1990.
Реализация Fletcher-16 на разных языках программирования (английский)
Питер Канковски: Хеш-функции: эмпирическое сравнение . 2009 г.

Индивидуальные доказательства

↑ In Memoriam Джона Флетчера . Национальная лаборатория Лоуренса Ливермора, по состоянию на 16 марта 2017 г.
↑ ^a^b^c^d^e Джон Г. Флетчер: Арифметическая контрольная сумма для последовательных передач . 1982, с. 248.
↑ Анастасия Накассис: Алгоритм обнаружения ошибок Флетчера: как его эффективно реализовать и как избежать наиболее распространенных ошибок. 1988, стр. 71f.
↑ Анастасия Накассис: Алгоритм обнаружения ошибок Флетчера: как его эффективно реализовать и как избежать наиболее распространенных ошибок. 1988, стр. 76f.
^ ^A^b^c Тереза К. Максино, Филип Дж. Купман: Эффективность контрольных сумм для встроенных сетей управления . 2009, с. 69.
^ Бетти Зальцберг: Модификация контрольной суммы Флетчера . В: IEEE Transactions on Communications . Том 31, выпуск 2, 1983 г., DOI: 10.1109 / TCOM.1983.1095789 , стр. 296.
↑ ^a^b Анастасия Накассис: Алгоритм обнаружения ошибок Флетчера: как реализовать его эффективно и как избежать наиболее распространенных ошибок. 1988, с. 65.
^ Кейт Склоуэр: Повышение эффективности вычисления контрольной суммы OSI . В: Обзор компьютерных коммуникаций . Том 19, выпуск 5, 1989 г., DOI: 10.1145 / 74681.74684 , стр. 32–43 (PDF; 524 kB).
↑ Джонатан Стоун, Майкл Гринвальд, Крейг Партридж, Джеймс Хьюз: Выполнение контрольных сумм и CRC над реальными данными . В: Транзакции IEEE / ACM в сети . Том 6, выпуск 5, 1998 г., DOI: 10.1109 / 90.731187 .
↑ Анастасия Накассис: Алгоритм обнаружения ошибок Флетчера: как его эффективно реализовать и как избежать наиболее распространенных ошибок. 1988, стр. 68, вывод см. В Приложении A, стр. 76 и далее.
^ Дуглас В. Джонс: Модуль без деления, учебное пособие . 2001 г.
↑ Анастасия Накассис: Алгоритм обнаружения ошибок Флетчера: как его эффективно реализовать и как избежать наиболее распространенных ошибок. 1988, Приложение D, стр. 84 и далее.
↑ Джон Кодис: Контрольная сумма Флетчера: исправление ошибок за небольшую плату . 1992, глава "Enter Fletcher".
↑ Анастасия Накассис: Алгоритм обнаружения ошибок Флетчера: как его эффективно реализовать и как избежать наиболее распространенных ошибок. 1988, с. 70, с. 72.
↑ Об используемом коде см. Gerard J. Holzmann: Design and Validation of Computer Protocols . Прентис Холл, 1991, ISBN 0-13-539925-4 , стр. 63.
^ Адриан Фаррел: Интернет и его протоколы: сравнительный подход . Морган Кауфманн, Сан-Франциско, 2004 г., ISBN 155860913X , стр. 181 ( ограниченный предварительный просмотр в Поиске книг Google).
^ Дж. Цвейг, К. Партридж: Параметры альтернативной контрольной суммы TCP . RFC 1146, 1990.
^ Л. Эггерт: Перемещение неразвернутых расширений TCP RFC 1072, RFC 1106, RFC 1110, RFC 1145, RFC 1146, RFC 1379, RFC 1644 и RFC 1693 в исторический статус . RFC 6247, 2011.
↑ Джеймс Гилфорд, Винод Гопал: Быстрое вычисление контрольных сумм Флетчера . Intel Data Center Group, 14 января 2016 г., Введение.
↑ Об используемом коде см. Матиас Люфт: Технический документ ERNW 65 - Внутреннее устройство APFS для судебного анализа . 16 апреля 2018 г., стр. 7е.
↑ Тереза К. Максино, Филип Дж. Купман: Эффективность контрольных сумм для встроенных сетей управления . 2009, с. 67.
↑ Анастасия Накассис: Алгоритм обнаружения ошибок Флетчера: как его эффективно реализовать и как избежать наиболее распространенных ошибок. 1988, стр. 65, формулы и их вывод см. В Приложении B, стр. 80 и далее.
↑ Тереза К. Максино, Филип Дж. Купман: Эффективность контрольных сумм для встроенных сетей управления . 2009, стр. 64f.
↑ Тереза К. Максино, Филип Дж. Купман: Эффективность контрольных сумм для встроенных сетей управления . 2009, с. 65.
^ Джон Г. Флетчер: Арифметическая контрольная сумма для последовательных передач . 1982, с. 251.
↑ Анастасия Накассис: Алгоритм обнаружения ошибок Флетчера: как его эффективно реализовать и как избежать наиболее распространенных ошибок. 1988, с. 73.
↑ Тереза К. Максино, Филип Дж. Купман: Эффективность контрольных сумм для встроенных сетей управления . 2009, с. 70.

Эта статья была добавлена в список отличных статей 1 июля 2017 года в этой версии .

[1] In Memoriam Джона Флетчера . Национальная лаборатория Лоуренса Ливермора, по состоянию на 16 марта 2017 г.

[fletcher248-2] Джон Г. Флетчер: Арифметическая контрольная сумма для последовательных передач . 1982, с. 248.

[3] Анастасия Накассис: Алгоритм обнаружения ошибок Флетчера: как его эффективно реализовать и как избежать наиболее распространенных ошибок. 1988, стр. 71f.

[4] Анастасия Накассис: Алгоритм обнаружения ошибок Флетчера: как его эффективно реализовать и как избежать наиболее распространенных ошибок. 1988, стр. 76f.

[maxino69-5] A^b^c Тереза К. Максино, Филип Дж. Купман: Эффективность контрольных сумм для встроенных сетей управления . 2009, с. 69.

[6] Бетти Зальцберг: Модификация контрольной суммы Флетчера . В: IEEE Transactions on Communications . Том 31, выпуск 2, 1983 г., DOI: 10.1109 / TCOM.1983.1095789 , стр. 296.

[nakassis65-7] Анастасия Накассис: Алгоритм обнаружения ошибок Флетчера: как реализовать его эффективно и как избежать наиболее распространенных ошибок. 1988, с. 65.

[8] Кейт Склоуэр: Повышение эффективности вычисления контрольной суммы OSI . В: Обзор компьютерных коммуникаций . Том 19, выпуск 5, 1989 г., DOI: 10.1145 / 74681.74684 , стр. 32–43 (PDF; 524 kB).

[9] Джонатан Стоун, Майкл Гринвальд, Крейг Партридж, Джеймс Хьюз: Выполнение контрольных сумм и CRC над реальными данными . В: Транзакции IEEE / ACM в сети . Том 6, выпуск 5, 1998 г., DOI: 10.1109 / 90.731187 .

[10] Анастасия Накассис: Алгоритм обнаружения ошибок Флетчера: как его эффективно реализовать и как избежать наиболее распространенных ошибок. 1988, стр. 68, вывод см. В Приложении A, стр. 76 и далее.

[11] Дуглас В. Джонс: Модуль без деления, учебное пособие . 2001 г.

[12] Анастасия Накассис: Алгоритм обнаружения ошибок Флетчера: как его эффективно реализовать и как избежать наиболее распространенных ошибок. 1988, Приложение D, стр. 84 и далее.

[13] Джон Кодис: Контрольная сумма Флетчера: исправление ошибок за небольшую плату . 1992, глава "Enter Fletcher".

[14] Анастасия Накассис: Алгоритм обнаружения ошибок Флетчера: как его эффективно реализовать и как избежать наиболее распространенных ошибок. 1988, с. 70, с. 72.

[15] Об используемом коде см. Gerard J. Holzmann: Design and Validation of Computer Protocols . Прентис Холл, 1991, ISBN 0-13-539925-4 , стр. 63.

[16] Адриан Фаррел: Интернет и его протоколы: сравнительный подход . Морган Кауфманн, Сан-Франциско, 2004 г., ISBN 155860913X , стр. 181 ( ограниченный предварительный просмотр в Поиске книг Google).

[17] Дж. Цвейг, К. Партридж: Параметры альтернативной контрольной суммы TCP . RFC 1146, 1990.

[18] Л. Эггерт: Перемещение неразвернутых расширений TCP RFC 1072, RFC 1106, RFC 1110, RFC 1145, RFC 1146, RFC 1379, RFC 1644 и RFC 1693 в исторический статус . RFC 6247, 2011.

[19] Джеймс Гилфорд, Винод Гопал: Быстрое вычисление контрольных сумм Флетчера . Intel Data Center Group, 14 января 2016 г., Введение.

[20] Об используемом коде см. Матиас Люфт: Технический документ ERNW 65 - Внутреннее устройство APFS для судебного анализа . 16 апреля 2018 г., стр. 7е.

[21] Тереза К. Максино, Филип Дж. Купман: Эффективность контрольных сумм для встроенных сетей управления . 2009, с. 67.

[22] Анастасия Накассис: Алгоритм обнаружения ошибок Флетчера: как его эффективно реализовать и как избежать наиболее распространенных ошибок. 1988, стр. 65, формулы и их вывод см. В Приложении B, стр. 80 и далее.

[23] Тереза К. Максино, Филип Дж. Купман: Эффективность контрольных сумм для встроенных сетей управления . 2009, стр. 64f.

[24] Тереза К. Максино, Филип Дж. Купман: Эффективность контрольных сумм для встроенных сетей управления . 2009, с. 65.

[25] Джон Г. Флетчер: Арифметическая контрольная сумма для последовательных передач . 1982, с. 251.

[26] Анастасия Накассис: Алгоритм обнаружения ошибок Флетчера: как его эффективно реализовать и как избежать наиболее распространенных ошибок. 1988, с. 73.

[27] Тереза К. Максино, Филип Дж. Купман: Эффективность контрольных сумм для встроенных сетей управления . 2009, с. 70.

Languages