Исследование вычислительной сложности формирования контрольных сумм для алгоритма CRC в зависимости от разрядности порождающего полинома

Турдиев Одилжан Акрамович

Постановка задачи: Необходимость обеспечения целостности данных, передаваемых в сетях связи, актуализирует вопрос обеспечения формирования контрольных сумм. При этом целесообразно снижение сложности алгоритмов формирования контрольных сумм для повышения целостности данных. Известный алгоритм формирования контрольных сумм CRC (Cyclic Redundancy Code) обладает высокой вычислительной сложностью. Целью работы является выполнение поисковых исследований для обоснования принципиальной возможности снижении вычислительной сложности алгоритма формирования контрольных сумм CRC и поиска возможных путей практической реализации. Научная новизна исследования заключается в том, что в первые рассматривается вычислительная сложность алгоритма CRC в зависимости от порождающих полиномов и их разрядности.

Ключевые слова:вычислительная сложность, порождающий полином, циклический избыточный код, пакетные ошибки, ошибочные биты, целостность.