IPB
ЛогинПароль:

 
 Ответить  Открыть новую тему 
> подсчет контрольной суммы CRC, полиномиальная арифметика
сообщение
Сообщение #1


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +


У меня есть примерный алгоритм по подсчету контрольной суммы, но он не до конца мне ясен. Кто сможет, объясните пожалуйста.
1. выбрать полином. Например если степень полинома 4, то можно выбрать полином 10011 (ну, а если степень полинома равна 8, то полином может быть думаю таким 100111111). т.е. степень полинома - это позиция самого старшего бита.
2. Затем код сообщения перевести в двоичную систему счисления. Здесь непонятно. Например если код полученного сообщения равен например 36 21 16, то что переводить в двоичную систему? их сумму, то бишь 36+21+16=73=1001001 или же сначала каждый символ переводить в двоичку а потом складывать, типа 36=100100
21=10101
16=10000 и теперь только складывать 100100+10101+10000=110101??
3.теперь нужно дополнить полученное сообщение нулями. если степень полинома 8, как в моем случае, то 8 нулями. предположим полученное сообщение это все-таки 110101 а не 1001001 ,тогда выравненное сообщение будет таким 11010100000000
4. теперь это выравненное сообщение нужно поделить (используя CRC арифметику) на полином, то бишь
11010100000000 надо поделить на 100111111 и найденный остаток и будет представлять собой контрольную сумму. Но как это вообще осуществить? это деление? у меня пока мало информации по этому поводу, знаю только, что там как-то замешаны XOR и сдвиги. Но этого мало, чтобы понять. =(

Сообщение отредактировано: Тёмный Эльф -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


2. посчитай внимательнее, и увидишь, что результат один и тот же.


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +


Цитата(мисс_граффити @ 2.05.2007 23:50) *

2. посчитай внимательнее, и увидишь, что результат один и тот же.


хе.. я глючу.. результат ДОЛЖЕН ПОЛУЧИТЬСЯ ОДИНАКОВЫМ.. rolleyes.gif

но что делать с 4. ? самый важный пункт в этом алгоритме! dry.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


Википедия (с примером. Правда, на с)


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +


Цитата(мисс_граффити @ 3.05.2007 0:30) *


Спасибо, я попробую разобраться. Хотя до конца все-равно не понятно как это деление происходит, программа такая короткая даже странно как-то!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


N337
****

Группа: Пользователи
Сообщений: 737
Пол: Мужской

Репутация: -  26  +


Цитата(Тёмный Эльф @ 3.05.2007 7:38) *

Спасибо, я попробую разобраться. Хотя до конца все-равно не понятно как это деление происходит, программа такая короткая даже странно как-то!

Деление упрощается до XOR и сдвигов, т. к. многочлен степени n с коэффициентами 0 и 1 - это просто (n+1)-разрядное двоичное число. По сути, CRC - развитие простого алгоритма подсчёта контрольной суммы через XOR.

Простое суммирование слов потока не даёт защиты от перестановки местами слов в потоке. Суммирование по модулю 2 (XOR) не зафиксирует ошибку, если ошибка в некотором бите каждого слова произошла чётное число раз. Алгоритм CRC защищён от таких случаев.

Выбор того или иного многочлена-делителя осуществляется на основе анализа возможной структуры потока, для которого будут считаться контрольные суммы. На практике используется несколько стандартных многочленов, например:
CRC-7 - x^7 + x^3 + 1 (используется в картах MMC и SD при передаче команд);
CRC-16-CCITT (CRC-CCITT) - x^16 + x^12 + x^5 + 1 (часто используется в телекоммуникационных протоколах: PPP, Bluetooth, IrDA, в моих радиомодемах smile.gif);
CRC-16-IBM (CRC-16) - x^16 + x^15 + x^2 + 1 (в USB);
CRC-32-MPEG2 - x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1 (в MPEG2/DVD).

Использование своего полинома-делителя требует математического обоснования эффективности обнаружения ошибки.

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

Сообщение отредактировано: xds -


--------------------
The idiots are winning.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +


Цитата
Деление упрощается до XOR и сдвигов, т. к. многочлен степени n с коэффициентами 0 и 1 - это просто (n+1)-разрядное двоичное число. По сути, CRC - развитие простого алгоритма подсчёта контрольной суммы через XOR.



И сколько же будет 11010100000000 поделить на 100111111? Эти числа нужно представить в виде многочленов и поделить друг на друга? Я не врубаюсь.. Хотелось бы понять как это вручную рассчитывается, в теории не все так ясно.

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


N337
****

Группа: Пользователи
Сообщений: 737
Пол: Мужской

Репутация: -  26  +


Вот перевод неплохой статьи про CRC: http://www.yasmax.net/download/CRC_Guide.pdf


--------------------
The idiots are winning.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Влюблённый псих
***

Группа: Пользователи
Сообщений: 185
Пол: Женский
Реальное имя: Лейла

Репутация: -  1  +


Цитата(xds @ 3.05.2007 19:23) *

Вот перевод неплохой статьи про CRC: http://www.yasmax.net/download/CRC_Guide.pdf


да..неплохая книга ,я читала её, но так и не поняла ,как это они так ловко просчитали!
1100001010 = частное (оно никого не интересует)
---------------
10011 ) 11010110110000 = выровненное сообщение (1101011011 + 0000)
=полином ,,.,.,,.,,....
10011,,.,,....
-----,,.,,....
10011,.,,....
10011,.,,....
-----,.,,....
00001.,,....
00000.,,....
-----.,,....
00010,,....
00000,,....
-----,,....
00101,....
00000,....
-----,....
01011....
00000....
-----....
10110...
10011...
-----...
01010..
00000..
-----..
10100.
10011.
-----.
01110
00000
-----
1110 = остаток = контрольная сумма!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


N337
****

Группа: Пользователи
Сообщений: 737
Пол: Мужской

Репутация: -  26  +


Суть в том, что можно договориться о вычитании по модулю 2 при делении многочленов. При этом теряются знаки при коэффициентах остатка (они всегда неотрицательны - 0 или 1), но это не принципиально для подсчёта КС, и , кроме того, упрощает реализацию.

Код
11010110110000 | 10011
10011          +----------
-----            1100001010
010011
.10011
.-----
.0000010110
......10011
......-----
......0010100
........10011
........-----
........001110


--------------------
The idiots are winning.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 15:32
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name