Ross Williams N

• Файл формата pdf
• размером 199,59 КБ

• Добавлен пользователем lay_2000. дата добавления неизвестна
• Отредактирован 20.10.2010 05:11
• Скачан 18 пользователями

Статья 1993 г.
Предисловие
Данная статья посвящена полному и точному описанию CRC (Cyclic Redundancy
Codes – Циклические Избыточные Коды) и реализации табличных алгоритмов их
вычисления. Большая часть литературы, касающаяся CRC вообще, и их табличным
разновидностям особенно, достаточно сложна и запутанна (по крайней мере, мне так
показалось). Статья была написана с целью дать простое и вместе с тем точное опи
сание CRC, вникающее во все тонкости реализации его высокоскоростных вариан
тов. Предложена параметрическая модель CRC алгоритма, названная "Rocksoft
Model CRC Algorithm", которая может быть настроена таким образом, чтобы рабо
тать подобно большинству стандартных реализаций алгоритмов расчета CRC, и ко
торая, одновременно, является хорошим примером для демонстрации особенностей
некоторых из них. Кроме того, приведен неоптимизированный пример на языке C, а
также 2 варианта высокоскоростной табличной реализации, и программа генерации
таблицы поиска для расчета CRC.

Оглавление.
Предисловие.
Введение: обнаружение ошибок.
Требования сложности.
Основная идея, заложенная в алгоритме CRC.
Полиномиальная арифметика.
Двоичная арифметика без учета переносов.
Полностью рабочий пример.
Выбор полинома.
Прямая реализация CRC.
Реализация табличного алгоритма.
Слегка преобразованный табличный алгоритм.
"Зеркальный" табличный алгоритм.
"Зеркальные" полиномы.
Начальные и конечные значения.
Полное определение алгоритма.
Параметрическая модель CRC алгоритма.
Каталог параметров стандартных реализаций CRC алгоритма.
Реализация модельного алгоритма.
Создай собственную табличную реализацию.
Генерация таблицы просмотра.
Резюме.
Поправки.
A. Словарь.
B. Ссылки.
C. Другие, обнаруженные мной, но не просмотренные ссылки.

• Чтобы скачать этот файл зарегистрируйтесь и/или войдите на сайт используя форму сверху.

Элементарное по crc алгоритмам обнаружения ошибок руководство

(Sams 2002) - MySQL and JSP Web Applications - Data-Driven Programming Using Tomcat and m5,1 MB 97. (Samsung).K9F6408U0B 8M nand-flash. Rar291,8 KB элементарное по crc алгоритмам обнаружения ошибок 98. (SanDisk).128Mbit nand Flash product manual rev1.1.rar239,6 KB 99. (SanDisk).CompactFlash memory card product manual rev10.0.rar482,4 KB 100. (SanDisk).FlashDrive product manual rev2.rar908,1 KB 101. (SanDisk).FlashDrive product manual rev4.0.rar266,1 KB 102. (SanDisk).SDP3B FlashDisk product manual rev7.1.rar690,6 KB 103. (SanDisk).TriFlash with MultiMediaCard interface product manual rev0.6.rar603,6 KB 104. (SanDisk).TriFlash with SD interface product manual rev1.2.rar669,4 KB 105. (SanDisk).USB CompactFlash, SD Card, MMC test commands user s guide. Rar305,5 KB 106. (TI).MSP430 Internet connectivity. Rar347,0 KB 107. (TI).Solid state voice recorder using. Tru64 unix. Command and Shell User s Guide (1999 en).pdf1,0 элементарное по crc алгоритмам обнаружения ошибок MB 45. - Tru64 unix.

Библиотека Ихтика _Компьютерная лит-ра. Файлов: 6705, Размер: 82,7 GB. ИмяРазмер d 2012.03_ihtik_comp-lib (6705)82,7 GB 1.

1. Общие положения. 1.1. Область применения методических рекомендаций. 1.2. Правовая база.

28. Методы стимулированияНаиболее известные и широко применимые с древних времен методы стимулирования это поощрение и наказание.

Циклический избыточный код Википедия

29 сентября 2012 В Крокус-экспо проходит очередная выставка Олдтаймер-галерея Смотреть фоторепортаж В Москве начал свою.

APC Back-UPS ES 400VA 230V Russian. APC Back-UPS ES 240 Watts / 400 элементарное по crc алгоритмам обнаружения ошибок VA, Входной. Land rover freelander бензин / дизель Книга по ремонту и эксплуатации. Руководство по ремонту Land Rover Freelander, инструкция по эксплуатации и техническому обслуживанию автомобилей Ленд Ровер Фриландер гг. Выпуска, оборудованных бензиновыми двигателями рабочим объемом 1,8, 2,5 л. а также дизельными двигателями рабочим объемом 2,0 л. Книга будет полезна владельцам автомобилей Ленд Ровер Фрилендер, механикам, специалистам СТО, ремонтных мастерских и автосервисов. Land rover freelander 2 с 2006 бензин / дизель Книга по ремонту и эксплуатации. Руководство по ремонту Ленд Ровер Фрилендер 2, руководство по эксплуатации и техническому обслуживанию, устройство Land Rover Freelander 2 с 2006 г. Выпуска, оборудованных бензиновыми двигателями рабочим объемом. M-Klasse (19972001) W 163; Verkaufsbezeichnung: M-Klasse: Produktionszeitraum: 19972005: Klasse: SUV: Karosserieversionen: Kombi: Motoren: Ottomotoren: 2,35. PDF-1.7БЦос 29.

Volkswagen Golf четвертого поколения, как всегда, внешне новый Golf претерпит по сравнению со старым не революционные, а эволюционные изменения. Поклонники немецкой машины увидят в новом автомобиле характерные «гольфовские» черты, например, широкую заднюю стойку крыши. Такой подход понятен: продающийся на протяжении многих лет в огромных количествах автомобиль не должен отпугивать людей какими-то непривычными решениями. К тому же Volkswagen Golf всегда блистал не столько дизайном, сколько безукоризненной техникой. А вот по части техники Golf четвертого поколения обновится как никогда. Так, новая платформа (на ней же выпу скаются Audi A3. Skoda Octavia, а позже появится seat Toledo увеличенные колесная база и колея обеспечат.

Элементарное руководство по CRC_алгоритмам обнаружения ошибок

Все, что Вы хотели бы знать о CRC_алгоритмах, но боялись спросить, опасаясь, что ошибки Ваших знаний могут быть обнаружены

Данная статья посвящена полному и точному описанию CRC (Cyclic Redundancy Codes – Циклические Избыточные Коды) и реализации табличных алгоритмов их вычисления.
Статья была написана с целью дать простое и вместе с тем точное описание CRC, вникающее во все тонкости реализации его высокоскоростных вариантов. Предложена параметрическая модель CRC алгоритма, названная "Rocksoft_Model CRC Algorithm", которая может быть настроена таким образом, чтобы работать подобно большинству стандартных реализаций алгоритмов расчета CRC, и которая, одновременно, является хорошим примером для демонстрации особенностей некоторых из них. Кроме того, приведен неоптимизированный пример на языке C, а также 2 варианта высокоскоростной табличной реализации, и программа генерации таблицы поиска для расчета CRC.

Книга в формате pdf

В целях противодействия нарушению авторских прав и права собственности, а также исключения необоснованных обвинений в адрес администрации сайта о пособничестве такому нарушению, администрация торговой площадки Plati (http://www.plati.com) обращается к Вам с просьбой - в случае обнаружения нарушений на торговой площадке Plati, незамедлительно информировать нас по адресу support@plati.com о факте такого нарушения и предоставить нам достоверную информацию, подтверждающую Ваши авторские права или права собственности. В письме обязательно укажите ваши контактные реквизиты (Ф.И.О. телефон).

В целях исключения необоснованных и заведомо ложных сообщений о фактах нарушения указанных прав, администрация будет отказывать в предоставлении услуг на торговой площадке Plati, только после получения от Вас письменных заявлений о нарушении с приложением копий документов, подтверждающих ваши авторские права или права собственности, по адресу: 123007, г. Москва, Малый Калужский пер. д.4, стр.3, Адвокатский кабинет «АКАР №380».

В целях оперативного реагирования на нарушения Ваших прав и необходимости блокировки действий недобросовестных продавцов, Plati просит Вас направить заверенную телеграмму, которая будет являться основанием для блокировки действий продавца, указанная телеграмма должна содержать указание: вида нарушенных прав, подтверждения ваших прав и ваши контактные данные (организиционно-правовую форму лица, Ф.И.О.). Блокировка будет снята по истечение 15 дней, в случае непредставления Вами в Адвокатский кабинет письменных документов подтверждающих ваши авторские права или права собственности.

Руководство По Crc Алгоритмам Обнаружения

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

Ведь если ошибка обнаружена, можно осуществить повторную передачу данных и решить проблему. Если исходный код по своей длине равен полученному коду, обнаружить ошибку передачи не предоставляется возможным. Можно, конечно, передать код дважды и сравнить, но это уже двойная избыточность. Простейшим способом обнаружения ошибок является контроль по четности. Обычно контролируется передача блока данных ( М бит ). Этому блоку ставится в соответствие кодовое слово длиной N бит.

Реализации алгоритмов /Циклический избыточный код 1 CRC -4; 2 CRC -8; 3 CRC -16; 4 CRC -32; 5 Программная реализация на C; 6 Примечания.

• Контроль по четности, CRC, алгоритм Хэмминга. Введение в коды вероятность обнаружения ошибки, но и выше избыточность).
• Cyclic redundancy check, CRC) — алгоритм нахождения контрольной суммы. Элементарное руководство по CRC алгоритмам обнаружения ошибок.

В статье приводится описание алгоритма подсчета контрольной суммы CRC. практически со 100% вероятностью, обнаруживать сбои при хранении и. CRC-алгоритмы обнаружения ошибок в транзакциях. [1] Ross N.Williams « Элементарное руководство по CRC алгоритмам обнаружения ошибок». 1. Обнаружение ошибок. 2. Необходимость использования сложных алгоритмов. 3. Основная идея CRC - алгоритмов. 4. Полиномиальная арифметика.

причем N>M. Избыточность кода характеризуется величиной 1-M/N. Вероятность обнаружения ошибки определяется отношением M/N (чем меньше это отношение. тем выше вероятность обнаружения ошибки, но и выше избыточность ). При передаче информации она кодируется таким образом, чтобы с одной стороны характеризовать ее минимальным числом символов, а с другой – минимизировать вероятность ошибки при декодировании получателем.

Для выбора типа кодирования важную роль играет так называемое расстояние Хэмминга. Пусть А и Б — две двоичные кодовые последовательности равной длины. Расстояние Хэмминга между двумя этими кодовыми последовательностями равно числу символов, которыми они отличаются. Например, расстояние Хэмминга между кодами 00111 и 10101 равно 2. Можно показать, что для детектирования ошибок в n битах схема кодирования требует применения кодовых слов с расстоянием Хэмминга не менее N + 1. Можно также показать, что для исправления ошибок в N битах необходима схема кодирования с расстоянием Хэмминга между кодами не менее 2N + 1.

Таким образом, конструируя код, мы пытаемся обеспечить расстояние Хэмминга между возможными кодовыми последовательностями большее, чем оно может возникнуть из-за ошибок. Широко распространены коды с одиночным битом четности. В этих кодах к каждым М бит добавляется 1 бит. значение которого определяется четностью (или нечетностью) суммы этих М бит.

Так, например, для двухбитовых кодов 00. 01. 10. 11 кодами с контролем четности будут 000.

Если в процессе передачи один бит будет передан неверно, четность кода из М+1 бита изменится. Предположим, что частота ошибок ( BER – Bit Error Rate ) равна р = 10 -4. В этом случае вероятность передачи 8 бит с ошибкой составит 1 – (1 – p) 8 = 7,9 х 10 -4. Добавление бита четности позволяет детектировать любую ошибку в одном из переданных битах. Здесь вероятность ошибки в одном из 9 битов равна 9p(1 – p) 8.

Вероятность же реализации необнаруженной ошибки составит 1 – (1 – p) 9 – 9p(1 – p) 8 = 3,6 x 10 -7. Таким образом, добавление бита четности уменьшает вероятность необнаруженной ошибки почти в 1000 раз. Использование одного бита четности типично для асинхронного метода передачи. В синхронных каналах чаще используется вычисление и передача битов четности как для строк, так и для столбцов передаваемого массива данных.

Такая схема позволяет не только регистрировать, но и исправлять ошибки в одном из битов переданного блока. Контроль по четности достаточно эффективен для выявления одиночных и множественных ошибок в условиях, когда они являются независимыми. При возникновении ошибок в кластерах бит метод контроля четности неэффективен, и тогда предпочтительнее метод вычисления циклических сумм ( CRC — Cyclic Redundancy Check ). В этом методе передаваемый кадр делится на специально подобранный образующий полином.

Дополнение остатка от деления и является контрольной суммой. В Ethernet вычисление CRC производится аппаратно. На рис. 4. 1 показан пример реализации аппаратного расчета CRC для образующего полинома R(x) = 1 + x 2 + x 3 + x 5 + x 7. В этой схеме входной код приходит слева.

Элементарное руководство по CRC_алгоритмам обнаружения ошибок

Все, что Вы хотели бы знать о CRC_алгоритмах, но боялись спросить, опасаясь, что ошибки Ваших знаний могут быть обнаружены

Данная статья посвящена полному и точному описанию CRC (Cyclic Redundancy Codes – Циклические Избыточные Коды) и реализации табличных алгоритмов их вычисления.
Статья была написана с целью дать простое и вместе с тем точное описание CRC, вникающее во все тонкости реализации его высокоскоростных вариантов. Предложена параметрическая модель CRC алгоритма, названная "Rocksoft_Model CRC Algorithm", которая может быть настроена таким образом, чтобы работать подобно большинству стандартных реализаций алгоритмов расчета CRC, и которая, одновременно, является хорошим примером для демонстрации особенностей некоторых из них. Кроме того, приведен неоптимизированный пример на языке C, а также 2 варианта высокоскоростной табличной реализации, и программа генерации таблицы поиска для расчета CRC.

Книга в формате pdf

Отзывов от покупателей не поступало

© Торговая площадка 3akup.ru

Руководство по CRC алгоритмам обнаружения ошибок

Данная статья посвящена полному и точному описанию CRC (Cyclic Redundancy Codes – Циклические Избыточные Коды) и реализации табличных алгоритмов их вычисления. Большая часть литературы, касающаяся CRC вообще, и их табличным разновидностям особенно, достаточно сложна и запутанна (по крайней мере, мне так показалось). Статья была написана с целью дать простое и вместе с тем точное опи сание CRC, вникающее во все тонкости реализации его высокоскоростных вариан тов. Предложена параметрическая модель CRC алгоритма, названная "Rocksoft Model CRC Algorithm", которая может быть настроена таким образом, чтобы рабо тать подобно большинству стандартных реализаций алгоритмов расчета CRC, и ко торая, одновременно, является хорошим примером для демонстрации особенностей некоторых из них. Кроме того, приведен неоптимизированный пример на языке C, а также 2 варианта высокоскоростной табличной реализации, и программа генерации таблицы поиска для расчета CRC.

Элементарное руководство по CRC алгоритмам обнаружения ошибок

Методы обнаружения ошибок предназначены для выявления повреждений со общений при их передаче по зашумленным каналам (вносящих эти ошибки). Для этого передающее устройство создает некоторое число, называемое контрольной суммой и являющееся функцией сообщения, и добавляет его к этому сообщению. Приемное устройство, используя тот же самый алгоритм, рассчитывает контроль ную сумму принятого сообщения и сравнивает ее с переданным значением. На пример, если мы для расчета контрольной суммы используем простое сложение байтов сообщения по модулю 256, то может возникнуть примерно следующая си туация. (Все числа примера десятичные.)

Как Вы видите, второй байт сообщения при передаче оказался измененным с 23 на 27. Приемник может обнаружить ошибку, сравнивая переданную контрольную сумму (33) с рассчитанной им самим: 6 + 27 + 4 = 37. Если при правильной пере даче сообщения окажется поврежденной сама контрольная сумма, то такое сооб щение будет неверно интерпретировано, как искаженное. Однако, это не самая плохая ситуация. Более опасно, одновременное повреждение сообщения и кон трольной суммы таким образом, что все сообщение можно посчитать достоверным. К сожалению, исключить такую ситуацию невозможно, и лучшее, чего можно до биться, это снизить вероятность ее появления, увеличивая количество информации в контрольной сумме (например, расширив ее с одного до 2 байт).

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

<исходное неизмененное сообщение> <контрольная сумма>

В предыдущем разделе мы показали, что повреждение сообщения может быть обнаружено, используя в качестве алгоритма контроля простое суммирование бай тов сообщения по модулю 256:

Сообщение с контрольной суммой

Сообщение после передачи

Недостаток этого алгоритма в том, что он слишком прост. Если произойдет не сколько искажений, то в 1 случае из 256 мы не сможем их обнаружить. Например:

всего снизит вероятность ошибки с 1/256 до 1/65536. Хотя это и неплохая идея, од нако, она имеет тот недостаток, что применяемая формула расчета не "случайна" в должной степени — каждый суммируемый байт оказывает влияние лишь на один байт суммирующего регистра, при этом ширина самого регистра не имеет никакого значения. Например, во втором случае суммирующий регистр мог бы иметь ширину хоть мегабайт, однако ошибка все равно не была бы обнаружена. Проблема может быть решена лишь заменой простого суммирования более сложной функцией, чтобы каждый новый байт оказывал влияние на весь регистр контрольной суммы.

Таким образом, мы сформулировали 2 требования для формирования надежной контрольной суммы:

Ширина: Размер регистра для вычислений должен обеспечивать изна чальную низкую вероятность ошибки (например, 32 байтный ре гистр обеспечивает вероятность ошибки 1/2 32 ).

Случайность: Необходим такой алгоритм расчета, когда каждый новый байт может оказать влияние на любые биты регистра.

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

3. Основная идея, заложенная в алгоритме CRC

С чего нам следует начать в наших поисках алгоритмов более сложных, чем про стое суммирование? На ум приходят самые экзотичные схемы. Мы могли бы соста

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

Однако, нам нет необходимости заходить столь далеко — надо всего лишь сменить арифметическое действие. Если сложение, очевидно, не пригодно для формирования эффективной контрольной суммы, то таким действием вполне может оказаться деле ние при условии, что делитель имеет ширину регистра контрольной суммы.

Основная идея алгоритма CRC состоит в представлении сообщения виде огром ного двоичного числа, делении его на другое фиксированное двоичное число и ис пользовании остатка этого деления в качестве контрольной суммы. Получив сооб щение, приемник может выполнить аналогичное действие и сравнить полученный остаток с "контрольной суммой" (переданным остатком).

Приведу пример. Предположим, что сообщение состоит из 2 байт (6, 23), как в предыдущем примере. Их можно рассматривать, как шестнадцатеричное число 0167h, или как двоичное число 0000 0110 0001 0111. Предположим, что ширина реги стра контрольной суммы составляет 1 байт, а в качестве делителя используется 1001, тогда сама контрольная сумма будет равна остатку от деления 0000 0110 0001 0111 на 1001. Хотя в данной ситуации деление может быть выполнено с использованием стандартных 32 битных регистров, в общем случае это не верно. Поэтому воспользу емся делением "в столбик", которому нас учили в школе (вспомнили?). Только на этот раз, оно будет выполняться в двоичной системе счисления:

В десятичное виде это будет звучать так: "частное от деления 1559 на 9 равно 173

Хотя влияние каждого бита исходного сообщения на частное не столь сущест венно, однако 4 битный остаток во время вычислений может радикально изменить ся, и чем больше байтов имеется в исходной сообщении (в делимом), тем сильнее меняется каждый раз величина остатка. Вот почему деление оказывается приме нимым там, где обычное сложение работать отказывается.

В нашем случае передача сообщения вместе с 4 битной контрольной суммой выгля дела бы (в шестнадцатеричном виде) следующим образом: 06172, где 0617 – это само со общение, а 2 – контрольная сумма. Приемник, получив сообщение, мог бы выполнить аналогичное деление и проверить, равен ли остаток переданному значению (2).

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

4. Полиномиальная арифметика

Ключевым словом, которое Вы будете постоянно слышать при работе с CRC, является слово "полином". Все CRC алгоритмы основаны на полиномиальных вы числениях, и для любого алгоритма CRC можно указать, какой полином он исполь зует. Что это значит?

Вместо представления делителя, делимого (сообщения), частного и остатка в ви де положительных целых чисел (как это было сделано в предыдущем разделе), можно представить их в виде полиномов с двоичными коэффициентами или в виде строки бит, каждый из которых является коэффициентом полинома. Например, десятичное число 23 в шестнадцатеричной системе счисления имеет вид 17, а в дво ичном – 10111, что совпадает с полиномом:

1*x^4 + 0*x^3 + 1*x^2 + 1*x^1 + 1*x^0

И сообщение, и делитель могут быть представлены в виде полиномов, с которы ми как и раньше можно выполнять любые арифметические действия; только теперь нам придется не забывать о иксах. Предположим, что мы хотим перемножить, на пример, 1101 и 1011. Это можно выполнить, как умножение полиномов:

(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)

+ x^3 + x^1 + x^0) = x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0

Теперь для получения правильного ответа нам необходимо указать, что Х равен 2, и выполнить перенос бита от члена 3*x^3. В результате получим:

x^7 + x^3 + x^2 + x^1 + x^0

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

А то, что если мы считаем, "X" нам не известен. то мы не можем выполнить пере нос. Нам не известно, что 3*x^3 – это то же самое, что и x^4 + x^3. так как мы не знаем, что X = 2. В полиномиальной арифметике связи между коэффициентами не установлены, и, поэтому, коэффициенты при каждом члене полинома становятся строго типизированными — коэффициент при x^2 имеет иной тип, чем при x^3 .

Если коэффициенты каждого члена полинома совершенно изолированы друг от друга, то можно работать с любыми видами полиномиальной арифметики, просто меняя правила, по которым коэффициенты работают. Одна из таких схем для нам чрезвычайно интересна, а именно, когда коэффициенты складываются по моду лю 2 без переноса – то есть коэффициенты могут иметь значения лишь 0 или 1, пе ренос не учитывается. Это называется "полиномиальная арифметика по модулю 2". Возвращаясь к предыдущему примеру:

(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)

= x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0

По правилам обычной арифметики, коэффициент члена 3*x^3 распределяется по другим членам полинома, используя механизм переноса и предполагая, что X = 2. В "полиномиальной арифметике по модулю 2" нам не известно, чему равен "X", переносов здесь не существует, а все коэффициенты рассчитываются по моду лю 2. В результате получаем:

= x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + x^0

Как пишет Д. Кнут [Knuth81, стр.400]. "Читатель может подметить сходство между полиномиальной арифметикой и арифметикой высокой точности (multiple precision arithmetic) (раздел 4.3.1.), когда основание b заменяется на x. Основное различие со

Элементарное руководство по CRC алгоритмам обнаружения ошибок

стоит в том, что коэффициент u k члена x k в полиномиальной арифметике считается ма лой величиной, или величиной, не связанной с ближайшими коэффициентами x k 1 (и x k+1 ), поэтому перенос от одного члена к другому в ней отсутствует. Фактически, поли номиальная арифметика по модулю b во многом аналогична арифметике высокой точ ности по основанию b за исключением подавления всех переносов."

Таким образом, полиномиальная арифметика по модулю 2 – это фактически двоичная арифметика по модулю 2 без учета переносов. Хотя полиномы имеют удобные математические средства для анализа CRC алгоритмов и алгоритмов кор рекции ошибок, для упрощения дальнейшего обсуждения они будут заменены на непосредственные арифметические действия в системе, с которой они изоморфны, а именно в системе двоичной арифметики без переносов.

Оставив полиномы вне поля нашего внимания, мы можем сфокусировать его на обычной арифметике, так как действия, выполняемые во время вычисления CRC, являются арифметическими операциями без учета переносов. Часто это называет ся полиномиальной арифметикой, но, как я уже говорил, о ней здесь больше уже не будет сказано ни слова, а вместо этого мы будет обсуждать арифметику CRC. А так как эта арифметическая система является ключевой часть расчетов CRC, нам луч ше заняться ею. Итак, начнем.

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

Для каждой пары битов возможны 4 варианта:

То же самое справедливо и для вычитания:

когда имеются также 4 возможные комбинации:

Фактически, как операция сложения, так и операция вычитания в CRC ариф метике идентичны операции "Исключающее ИЛИ" (eXclusive OR – XOR), что по зволяет заменить 2 операции первого уровня (сложение и вычитание) одним дейст вием, которое, одновременно, оказывается инверсным самому себе. Очень удоб ное свойство такой арифметики.

Сгруппировав сложение и вычитание в одно единое действие, CRC арифметика исключает из поля своего внимания все величины, лежащие за пределами самого старшего своего бита. Хотя совершенно ясно, что значение 1010 больше, чем 10, это оказывается не так, когда говорят, что 1010 должно быть больше, чем 1001.

8 5. Двоичная арифметика без учета переносов

Чтобы понять почему, попытайтесь получить из 1010 значение 1001, отняв или при бавив к нему одну и ту же величину:

1001 = 1010 + 0011

1001 = 1010 - 0011

Это сводит на нет всякое представление о порядке.

Определив действие сложения, перейдем к умножению и делению. Умноже ние, как и в обычной арифметике, считается суммой значений первого сомножите ля, сдвинутых в соответствии со значением второго сомножителя.

1111111 Обратите внимание: при суммировании используется CRC сложение

Деление несколько сложнее, так как нам требуется знать, когда "одно число превращается в другое ". Чтобы сделать это, нам потребуется ввести слабое поня тие размерности: число X больше или равно Y, если позиция самого старшего еди ничного бита числа X более значима (или соответствует) позиции самого старшего единичного бита числа Y. Ниже приведен пример деления (пример заимствован из [Tanenbaum81]).

В результате получаем частное, которое нас не интересует и, поэтому, отбрасы вается за ненадобностью, и остаток, который и используется в качестве контроль ной суммы. Расчет закончен.

Как правило, контрольная сумма добавляется к сообщению и вместе с ним пе редается по каналам связи. В нашем случае будет передано следующее сообщение: 11010110111110.

На другом конце канала приемник может сделать одно из равноценных действий: 1. Выделить текст собственно сообщения, вычислить для него контрольную сумму (не забыв при этом дополнить сообщение W битами), и сравнить ее с

2. Вычислить контрольную сумму для всего переданного сообщения (без добав ления нулей), и посмотреть, получится ли в результате нулевой остаток.

Оба эти варианта совершенно равноправны. Однако, в следующем разделе мы будет работать со вторым вариантом, которое является математически более пра вильным.

Таким образом, при вычислении CRC необходимо выполнить следующие действия: 1. Выбрать степень полинома W и полином G (степени W).

2. Добавить к сообщению W нулевых битов. Назовем полученную строку M'.

3. Поделим M' на G с использованием правил CRC арифметики. Полученный остаток и будет контрольной суммой.

Элементарное руководство по CRC алгоритмам обнаружения ошибок, Автор неизвестен

Данная статья посвящена полному и точному описанию CRC (Cyclic Redundancy Codes – Циклические Избыточные Коды) и реализации табличных алгоритмов их вычисления. Большая часть литературы, касающаяся CRC вообще, и их табличным разновидностям особенно, достаточно сложна и запутанна (по крайней мере, мне так показалось). Статья была написана с целью дать простое и вместе с тем точное описание CRC, вникающее во все тонкости реализации его высокоскоростных вариантов. Предложена параметрическая модель CRC алгоритма, названная "Rocksoft Model CRC Algorithm", которая может быть настроена таким образом, чтобы работать подобно большинству стандартных реализаций алгоритмов расчета CRC, и которая, одновременно, является хорошим примером для демонстрации особенностей некоторых из них. Кроме того, приведен неоптимизированный пример на языке C, а также 2 варианта высокоскоростной табличной реализации, и программа генерации таблицы поиска для расчета CRC.

Книга «Элементарное руководство по CRC алгоритмам обнаружения ошибок» автора Автор неизвестен оценена посетителями КнигоГид, и её читательский рейтинг составил 3.20 из 5.
Для бесплатного просмотра предоставляются: аннотация, публикация, отзывы, а также файлы на скачивания.
В нашей онлайн библиотеке произведение Элементарное руководство по CRC алгоритмам обнаружения ошибок можно скачать в форматах epub, fb2, pdf, txt, html или читать онлайн.
Работа Автор неизвестен «Элементарное руководство по CRC алгоритмам обнаружения ошибок» принадлежит к жанру «Радиоэлектроника» .

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

Радиоконструктор 2002-05 Автор неизвестен

Радиоконструктор 2002-04 Автор неизвестен

Радиоконструктор 2002-06 Автор неизвестен

Вы можете внести посильный вклад в развитие сайта КнижныйГид рассказав о нас друзьям в социальных сетях:

После скачивания Вы сможете открыть книгу «Элементарное руководство по CRC алгоритмам обнаружения ошибок» на большинстве современных устройств. Выберите подходящий формат файла, перенесите его на электронную книгу/электронную читалку, на телефон или смартфон (работающий на android, iOS и пр.), на iPad или иной планшет, на iPhone, iPod, компьютер (ПК, PC) или отправьте документ на печать, если предпочитаете работать с бумажным носителем.

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

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

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

Если вы обнаружили незаконные материалы или нарушение авторских прав, то просим вас прислать жалобу.