|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/128 26 Jun 2001 13:06:02
To : All
Subject : CRC64: информация к размышлению
--------------------------------------------------------------------------------
Replying to a message of Max Alekseyev to All:
MA> Есть ли стандарт (хотя бы де-факто) на полином в алгоритме CRC64?
Так как никто не поторопился с ответом на мой вопрос, пришлось самому
изыскивать ответ. Спешу поделиться тем, что мне удалось узнать.
Hачну с выбора полинома. Существуют два подхода:
Первый заключается в выборе примитивного полинома. а этом настаивают Numerical
Recipes (http://www.nr.com), .20.3 Cyclic Redundancy and Other Checksums. CRC с
таким полиномом способна обнаруживать ошибки в не более <степень полинома>
последовательных битах.
Второй подход, описываемый в статье
Ross N. Williams "A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS"
(ftp://ftp.adelaide.edu.au/pub/rocksoft/crc_v3.txt), наоборот, предлагает
выбирать полином как произведение специально подобранных полиномов меньших
степеней. В частности, в это произведение должен входить полином (x+1), что дает
возможность распознавать однобитовые ошибки.
Оба подхода имеют свои преимущества, хотя если исходить только из указанных
источников, второй кажется значительно более изощренным применительно к
обнаружению различного рода ошибок.
Замечу, что полином 0xEDB88320 ставший стандартом де-факто для CRC32, является
примитивным.
Кстати, имеется перевод статьи Williams'а на русский язык - прекрасный с
художественной точки зрения, но просто ужасный с терминологической (особенно
меня "убил" как раз перевод параграфа о выборе полинома). Этот перевод доступен
по ссылкам
http://dore.on.ru/articles/crcguide.pdf
http://www.uic.nnov.ru/~ryai/d/CRCguide.rar
Теперь собственно о CRC64. Покопавшись в дебрях интернета, я обнаружил как
минимум три распространенных разновидности:
1) Эта CRC64 берет свое начало с заметки
http://apollo.backplane.com/matt/crc64.html
а нее имеется много ссылок в интернете и готовых исходников типа
http://www.gtk.org/~trog/gcrc-0.1.tar.gz
Полином здесь не является примитивным, но и насколько он удовлетворяет
требованиям из статьи Williams'а никакой информации не имеется.
2) Другая CRC64 используется в генетических базах данных SWISS-PROT. Что это
такое, я сказать затрудняюсь, но судя по ссылкам это достаточно распространенная
вещь (в узких кругах? ;). Ее авторы следовали указаниям именно Numerical Recipes
и даже полином взяли оттуда:
x^64 + x^4 + x^3 + x^1 + 1 (0xD800000000000000).
Реализация практически один в один совпадает с классической CRC32, за
исключением разрядности. Исходные тексты можно найти здесь:
ftp://ftp.ebi.ac.uk/pub/software/swissprot/Swissknife/SPcrc.tar.gz
3) Полином из DLT (digital linear tape) стандарта ECMA-182
http://www.ecma.ch/ecma1/STAND/ECMA-182.HTM (стр. 63)
Судя по всему, предлагаемый здесь полином, наиболее удовлетворяет требованиям
описанным в статье Williams'а.
С интересным обсужденим последних двух CRC64 можно познакомиться здесь:
http://www.geocrawler.com/mail/msg.php3?msg_id=5330090&list=10
Regards, ш.ш
Max ~
--- FleetStreet 1.27.3.6
* Origin: Иглы лучей опять найдут нашу кровь. (2:5015/128)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
