Jump to content

    

Как из полинома получить сишный код

Recommended Posts

uriy

Имеется полином, порождающая матрица и кусок кода. 

Часто вижу подобное в помехоустойчивых кодах, но не понимаю как из этой математики получать код.

Для меня тут только понятно как получили данные в массиве.

Почему data проверяют побитно и причем тут операция исключающее или?

Что за результат полинома 471? Еще и в восьмеричной системе судя по всему. Как это учитывается в сишном коде?

unsigned int G[7] = {0x804f, 0x411e, 0x21b7, 0x11e2, 0x09c9, 0x04e5, 0x0273};

unsigned int Encode (unsigned int data)
{
    signed int i = 0;
    unsigned int checkbit = 0;

    for (i = 0; i < 7; i++)      
    {
        if (data & 0x8000)       
        {
            checkbit ^= G[i];      
        }
        data <<= 1;            
    }

    return (checkbit);
}

 

matrix.png

Share this post


Link to post
Share on other sites

_4afc_

х8543+1 = 2^8+2^5+2^4+2^3+2^0 =  100000000+100000+10000+1000+1 = 100111001

 

из двоичной в восьмиричную переводят так: 100111001 = 100_111_001 = 471

 

из двоичной в шестнадцатиричную переводят так: 100111001 = 1_0011_1001 = 139

Share this post


Link to post
Share on other sites

Lmx2315
Цитата

Почему data проверяют побитно и причем тут операция исключающее или?

http://kpe.hww.ru/ASM/Book/Charter9/1.htm

на рисунке Рис. 9.4. Схема вычисления CRC-деления.

Там представлена схема деления входного кода на полином чтобы получить остаток, так вот если приглядеться к процессу деления - то видно что его проделывают через "исключающее или"  и посредством сдвига на 1 бит.

Share this post


Link to post
Share on other sites

MegaVolt
1 час назад, Lmx2315 сказал:

Там представлена схема деления входного кода на полином чтобы получить остаток, так вот если приглядеться к процессу деления - то видно что его проделывают через "исключающее или"  и посредством сдвига на 1 бит.

Причём это самый медленный способ реализации. Далее идёт табличный который позволяет обрабатывать входящие данные не побитно а байтами и более. Плавный переход тут:

 

https://xakep.ru/2004/03/30/21788/

 

 

Share this post


Link to post
Share on other sites

Obam

Классику, классику жанра забыли!!! Ross N. Williams
http://ad-books.narod.ru/asm/articles/crc.pdf
Чуть-чуть не 30 лет уж как...

Share this post


Link to post
Share on other sites

uriy

Ключевая фраза в этих статьях - "Полиномиальная арифметика по модулю 2". Кое-что прояснилось.

Но прочитав эти статьи мне все равно бы не удалось написать такой сишный код как в первом посте.

Share this post


Link to post
Share on other sites

Darth Vader
10 часов назад, uriy сказал:

мне все равно бы не удалось написать такой сишный код как в первом посте.

Этот код тоже не идеален. Там есть поле для рефакторинга. Если массив G[7] нигде больше не используется, то логично объявить его локально внутри функции с квалификатором static const.

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.